[BOJ-11657]타임머신

이 문제는 벨만포드 알고리즘을 사용하는 문제이다.

1. 1번 도시로 부터 시작해서 2,.... n-1, n 번 도시 까지 

최단 경로가 존재하면 최단경로를 출력, 

최단 경로가 존재하지 않는 경우 (= 도달하지 못하는 INF으로 값이 되어 있는 경우) 에는 -1을 출력한다.

2. 그러나 이동 경로 중 음의 사이클이 존재하는 경우 그냥 -1을 출력한다.

벨만포드 알고리즘은 

정점1 에서 정점n 까지 이동할 때 최대 간선의 수는 n-1 일 것이다. 

loop 1 : 그렇기 때문에 n-1번 loop를 돌아 첫 시작위치부터 값을 계속 갱신하고, 

loop 2 : 음의 사이클이 존재하는 지 판정을 하는 loop를 돌린다.

#include<cstdio>
#include<vector>
#include<utility>
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
using namespace std;
typedef long long LLD;
typedef pair<LLD,LLD> PLL;
typedef vector<PLL> VPLL;
typedef vector<LLD> VLL;
VPLL path[505];
VLL dist;
const LLD INF = 1LL<<55;
int main(){
    int n, m;
    scanf("%d%d", &n ,&m);
    dist = VLL(n+1,INF);
    for(int i = 0 ; i < m ; i++){
        LLD u, v, w;
        scanf("%lld%lld%lld", &u, &v, &w);
        path[u].pb(mp(v,w));
    }
    dist[1] = 0;
    for(int v = 0 ; v < n-1 ; v++){
        for(int here = 1 ; here <= n ; here++){
            for(auto iter = path[here].begin(); iter != path[here].end() ; iter++){
                PLL p = *iter;
                LLD there = p.first;
                LLD cost = p.second;
                if(dist[here] != INF &&
                    dist[there] > dist[here] + cost){
                    dist[there] = dist[here] + cost;
                }
            }
        }
    }
 
    int non = 0;
    for(int here = 1 ; here <= n ; here++){
        for(auto iter = path[here].begin(); iter != path[here].end() ; iter++){
            PLL p = *iter;
            LLD there = p.first;
            LLD cost = p.second;
            if(dist[here] != INF &&
                dist[there] > dist[here] + cost){
                dist[there] = dist[here] + cost;
                non++;
            }
        }
    }
 
    if(non) puts("-1");
    else{
        for(int i = 2 ; i <= n ; i++){
            if(dist[i] == INF) puts("-1");
            else printf("%lld\n",dist[i]);
        }
    }
 
    return 0;
}