프로그래밍

www.acmicpc.net/problem/11657

[난이도] Gold4

[유형] Bellman-Ford

[풀이]

음의 가중치가 있는데 최단 경로를 구해야 하는 경우는 벨만포드 또는 플로이드 워셜 이용. 벨만포드 : V*E 플로이드 워셜 : V^3이므로 벨만포드를 이용한다. 최단 경로의 간선수는 최대 V-1개이기 때문에 V-1번 루프를 돌면서 최단 경로를 갱신해준다.

#include <cstdio>
#include <vector>
using namespace std;
using ll = long long;
int N,M;
vector<pair<int,ll>> adj[501];
ll dist[501],inf=1e18;
int main(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<M;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        adj[a].push_back({b,c});
    }

    for(int i=1;i<=N;i++) dist[i] = inf;
    dist[1] = 0;
    bool cycle = 0;
    for(int i=0;i<N;i++){
        for(int j=1;j<=N;j++){
            for(auto& p : adj[j]){
                int nxt = p.first, cost=p.second;
                if(dist[j] != inf && dist[nxt] > dist[j]+cost){
                    dist[nxt] = dist[j]+cost;
                    if(i==N-1) cycle = 1;
                }
            }
        }
    }
    if(cycle) puts("-1");
    else{
        for(int i=2;i<=N;i++) printf("%lld\n",dist[i]==inf ? -1 : dist[i]);
    }
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/11657.cpp