[BOJ] 11657. 타임머신 (C++)

문제

N개의 도시가 있다.

한 도시에 출발해서 다른 도시에 도착하는 버스가 M가 있다.

이때 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다.

1번 도시에서 출발해 2번 도시, 3번 도시, ..., N번 도시로 가는 가장 빠른 시간을 순서대로 출력

해당 도시로 가는 경로가 없다면 -1 출력

만약 1번 도시에서 출발해 어떤 도시로 가는 시간을 무한히 오래 전으로 되돌릴 수 있으면 첫 줄에 -1 출력

생각할 것

1. 문제에서 시간 C가 양수가 아닌 경우가 있고, 특정 도시에서 출발하므로 벨만 포드 알고리즘을 사용하자
2. 시간을 무한히 오래 전으로 되돌릴 수 있다 → 음수 사이클의 경우 판별하자
3. 제출 중에 계속 출력 초과가 떴다.
   1. 문제의 조건 : N (1 ≤ N ≤ 500), M (1 ≤ M ≤ 6,000), -10,000 ≤ C ≤ 10,000
   2. 음수 사이클이 있어 계산을 N번 반복한다면 INT범위보다 작은 언더플로우가 발생할 수 있다.
   3. 따라서 dist배열의 자료형을 long long으로 설정하고, INF를 LONG_LONG_MAX로 설정했다.

코드

#include <iostream>
#include <vector>
#include <tuple>
#include <climits>

using namespace std;

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

    int N, M, A, B, C;
    cin >> N >> M;

    // 인접 리스트
    vector<vector<pair<int, int>>> adj(N + 1);
    for (int i = 0; i < M; i++) {
        cin >> A >> B >> C;
        adj[A].push_back({B, C});
    }

    // 벨만 포드
    vector<long long> dist(N + 1, LONG_LONG_MAX);
    dist[1] = 0; // 시작 정점
    bool updated = false;
    for (int v = 0; v < N; v++) {
        updated = false;
        for (int cur = 1; cur <= N; cur++) { // cur 도시를 1부터 N까지 탐색해야 한다!
            for (int j = 0; j < adj[cur].size(); j++) {
                int next = adj[cur][j].first;
                int nextCost = adj[cur][j].second;
                if (dist[cur] == LONG_LONG_MAX) continue; // 업데이트 된 경로만 탐색
                if (dist[next] > dist[cur] + nextCost) {
                    dist[next] = dist[cur] + nextCost;
                    updated = true;
                }
            }
        }
        if (!updated) break;
    }

    if (updated) cout << -1; // 음수 사이클이 있는 경우
    else {
        for (int i = 2; i < dist.size(); i++) { // 각 도시로 가는 최단 시간
            if (dist[i] == LONG_LONG_MAX) cout << -1 << "\\n";
            else cout << dist[i] << "\\n";
        }
    }

    return 0;
}