[11657번] Time Machine 타임머신 - Bellman-Ford Algorithm[C++]☆

https://www.acmicpc.net/problem/11657

이 문제는 최단경로 문제이다. 보통은 다익스트라(Dijstra) 알고리즘을 쓰지만 이 문제의 경우에는 경로 가중치가 음수인 경우가 있으므로

벨만-포드(Bellman-Ford) 알고리즘 또는 플로이드-워셜(Floyd-Warshall) 알고리즘을 이용해야 한다.

두 개의 차이점은 구현 면에서 보면 플로이드-워셜은 이해하기는 힘드나 구현은 간단하다.

벨만-포드는 이해하기도 쉽고 구현도 그렇게 어렵지는 않지만 플로이드-워셜에 비하면 좀 더 복잡하다.

다음 시간 복잡도 면에서 보면, 벨만-포드는 O(E*V)이고 플로이드-워셜은 O(V^3)이다.

주어진 문제(E = 6000, V = 500)에 대입하면,

벨만-포드는 O(E*V) = 3000000정도이고 플로이드-워셜은 O(V^3) = 125000000정도로 시간 제한이 1초인것을 감안하면

플로이드-워셜은 시간 초과가 날 가능성이 높다.

그러므로 벨만-포드 알고리즘을 이용할 것이다.

https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

(위키피디아 Bellman-Ford Algorithm)

https://ko.wikipedia.org/wiki/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

(위키백과 벨만-포드 알고리즘)

이 문제 난이도 면에서 보면 어렵지는 않으나

벨만-포드 알고리즘을 실제로 구현해보는 문제로 괜찮은 문제이다.

#include <cstdio>
#pragma warning (disable : 4996)
struct Edge {
    int to;
    int from;
    int weight;
};
Edge edge[6001];
int dist[501];
int main() {
    int N, M;
 
    bool NegativeCycleExist = false;    // 시작점에서 도달 가능한 타임머신으로 되어있는 사이클이 존재해 가장 빠른 시간이 존재하지 않는 경우
 
    scanf("%d %d", &N, &M);
    for (int i = 0; i <= N; i++)
        dist[i] = 0x07ffffff;            // 무한대 값이라 가정
    for (int i = 0; i < M; i++)
        scanf("%d %d %d", &edge[i].from, &edge[i].to, &edge[i].weight);
    dist[1] = 0;
    for (int i = 0; i < N - 1; i++) {    // N-1번 실행
        for (int j = 0; j < M; j++) {
            if (dist[edge[j].to] > dist[edge[j].from] + edge[j].weight) {
                dist[edge[j].to] = dist[edge[j].from] + edge[j].weight;
            }
        }
    }
    for (int i = 0; i < M; i++) {
        if (dist[edge[i].to] > dist[edge[i].from] + edge[i].weight) {
            NegativeCycleExist = true;
        }
    }
    if (NegativeCycleExist) {
        printf("-1\n");
        return 0;
    }
    for (int i = 2; i <= N; i++) {
        if (dist[i] == 0x07ffffff)
            printf("-1\n");
        else
            printf("%d\n", dist[i]);
    }
 
    return 0;
}