[백준] 11657번 타임머신

[적용한 알고리즘]

밸만포드

 

[아이디어]

 

 

[생각의 흐름 / 절차] 

내용

 

[교훈]

기본 문항이다. 음의 사이클을 어떻게 판단하는지 유심히 살펴보자.

참으로 유용한 블로그이다.

(http://kks227.blog.me/220796963742) 에서 배워감

 

<코드>

#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
#define MAX 501
using namespace std;
typedef pair<int, int> P;
const int INF = 1000000000;

int main(){
    int N, M, dist[MAX];
    scanf("%d %d", &N, &M);
    vector<P> adj[MAX];

    for (int i = 0; i < M; i++){
        int from, to, cost;
        scanf("%d %d %d", &from, &to, &cost);
        adj[from].push_back(P(to, cost)); // from->to , -> cost
    }

    bool minusCycle = false;
    fill(dist, dist + N + 1, INF);
    dist[1] = 0;

    for (int i = 1; i <= N; i++){
        for (int j = 1; j <= N; j++){
            for (auto &p : adj[j]){ // j번에 연결된 애들
                int nxt = p.first;
                int nxt_cost = p.second;

                if (dist[j] != INF && dist[nxt] > dist[j] + nxt_cost){
                    dist[nxt] = dist[j] + nxt_cost;
                    if (i == N){
                        //맨 마지막에 루프를 한 번 더 돌아서 최단거리가 갱신되는지 확인을 해줘야함.
                        //음의 사이클이 존재하는지 판별가능.
                        minusCycle = true;
                    }
                }
            }
        }
    }

    if (minusCycle){
        printf("-1\n");
        return 0;
    }

    for (int i = 2; i <= N; i++){
        if (dist[i] == INF) printf("-1\n");
        else printf("%d\n", dist[i]);
    }

    return 0;
}