타임머신

백준 11657번: 타임머신

아이디어

음의 간선이 존재하기 때문에 다익스트라 알고리즘으로는 최단거리를 찾을 수 없다. 따라서 O(VE)로 모든 경우의 수를 탐색하는 벨만 포드 알고리즘이 적합.

코드

#include <bits/stdc++.h>

using namespace std;

constexpr int MAX = 501;
constexpr long long INF = 1e18;
int N, M;
vector<pair<int, long long>> adj[MAX];
long long dist[MAX];

void solve() {
    fill(dist, dist+MAX, INF);
    dist[1] = 0;
    bool sw = false;
    for (int i = 0; i < N; i++) {
        for (int j = 1; j < N+1; j++) {
            for (auto p : adj[j]) {
                int next = p.first;
                long long nc = p.second;
                // dist[j] == INF, dist[next] == INF, nc < 0 인 경우 갱신이 되지 않도록 dist[j] != INF일 때만 갱신
                if (dist[j] != INF && dist[next] > dist[j]+nc) {
                    dist[next] = dist[j]+nc;
                    if (i == N-1) sw = true;
                }
            }
        }
    }
    if (sw) {
        cout << -1 << '\n';
    }
    else {
        for (int i = 2; i < N+1; i++) {
            if (dist[i] == INF) cout << -1 << '\n';
            else cout << dist[i] << '\n';
        }
    }
}

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

    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back({b, c});
    }
    solve();
    return 0;
}

여담

i가 1씩 커질때마다 싸이클을 한번씩 돈다고 하면, 500바퀴 돌렸을 때 INT_MIN보다 값이 작아질 수 있다. long long으로 써야함.