[백준/C++] 11657. 타임머신

 

1. 아이디어

1) 음의 가중치가 존재하고, 문제 자체가 음의 사이클 또한 염두하고 있기 때문에 해당 문제는 벨만-포드 알고리즘을 사용하는 것이라고 볼 수 있습니다.

 

2) 즉, 1번 노드에서 출발하여 그래프에 대해서 최단 거리를 갱신한 뒤 문제의 요구에 맞게 출력을 하면 되겠습니다.

 

3) 음의 사이클을 분별하는 방법은

벨만 포드 알고리즘의 결과 dist 배열과

벨만 포드 루프를 1번 더 돌린 dist 배열이 다를경우 음의 사이클 이라고 판단할 수 있습니다.

2. 주의할 점

1) 가중치의 경우의 수가 int 오버플로를 발생시킬 수 있기 떄문에 long long 이나 __int64를 사용해야 합니다.

2) 1번 노드에서 그 어떤 노드로 간선이 존재하지 않는 경우에는 그래프에 음의 사이클이 존재하던 말던,

-1 을 N-1 개 만큼 출력해야 합니다.

 

3. 솔루션

#include <iostream>
#include <vector>
#include <algorithm>
#define INF 2'000'000'000
using namespace std;
using int64 = long long;

struct Edge {
    int from, to, w;
};
vector<Edge> edges;
int N, M;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;

    edges.resize(M);
    for (int i = 0; i < M; ++i) {
        cin >> edges[i].from >> edges[i].to >> edges[i].w;
    }

    // 예외처리: 시작 노드에서 출발하는 간선이 없으면 모든 노드에 -1 출력
    {
        bool t = any_of(edges.begin(), edges.end(), [](const Edge& e) {
            return e.from == 1;
            });

        if (!t) {
            for (int i = 2; i <= N; ++i) {
                cout << -1 << '\n';
            }
            return 0;
        }
    }

    vector<int64> dist(N + 1, INF);
    dist[1] = 0;

    // 벨만 포드 알고리즘
    for (int i = 0; i < N - 1; ++i) {
        for (const auto& e : edges) {
            if (dist[e.from] < INF) {
                dist[e.to] = min(dist[e.to], dist[e.from] + e.w);
            }
        }
    }

    // 사이클 검사
    bool isCycle = false;
    for (const auto& e : edges) {
        if (dist[e.from] < INF && dist[e.from] + e.w < dist[e.to]) {
            isCycle = true;
            break;
        }
    }

    if (isCycle) {
        cout << "-1";
        return 0;
    }

    // 결과 출력
    for (int i = 2; i <= N; ++i) {
        if (dist[i] == INF) {
            cout << -1 << '\n';
        }
        else {
            cout << dist[i] << '\n';
        }
    }

    return 0;
}