문제

문제 링크

어떻게 접근할 것인가

  • 이 문제는 대놓고 벨만포드를 이용하라고 하는 문제이다.

유의할 점

  • 초기값이 무한대인데 무한대인 경우에는 연산에 들어가지 않도록 배제시켜주자!

코드

#include <cstdio>
#include <vector>
#define INF 5000000
using namespace std;

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    vector< vector<long long> > e(m, vector<long long>(3));
    vector<long long> dist(n+1, INF);
    for(int i = 0; i < m; i++){
        scanf("%lld %lld %lld", &e[i][0], &e[i][1], &e[i][2]);
    }
    dist[1] = 0;

    for(int k = 1; k < n; k++){
        for(int i = 0; i < m; i++){
            int u = e[i][0], v = e[i][1], w = e[i][2];
            if(dist[u] == INF)continue;
            if(dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w; 
            }
        }
    }

    for(int i = 0; i < m; i++){
        if(dist[e[i][0]] == INF)continue;
        if(dist[e[i][1]] > dist[e[i][0]] + e[i][2]){
            printf("-1");
            return 0;
        }
    }
    for(int i = 2; i < n + 1; i++){
        if(dist[i] < INF)printf("%lld\n", dist[i]);
        else printf("-1\n");
    }
    
}

느낀점

  • 무한대가 진짜 무한대가 아니라는게 함정이었다.
  • 다음 벨만포드 문제를 풀 때에도 유의해야겠다.