골목길

백준 1738번: 골목길

아이디어

음의 간선을 포함한 최단거리 찾기.
이 때 단순히 사이클이 존재한다고 -1을 출력하는 것이 아니라, 1부터 N까지 가는 길에 사이클이 존재하여 N에 도착했을 때 금품을 무한히 가질 수 있는 경우에만 -1을 출력해야 한다.
예를 들어, N=5이고, 1->2, 2->3, 3->4, 4->3, 1->5의 간선을 가진다고 하자. 3->4, 4->3이 음의 사이클이라고 해도, 1부터 N까지 가는 길은 1->5이고 3, 4에서 금품을 무한히 가진다 해도 그 상태로 N에 도달할 수 없기 때문에 -1을 출력하면 안 된다.

어떻게 하면 N까지 가는 길에 사이클이 존재하는지 판별할 수 있을까?
사이클이 존재하는 경우 해당 노드의 dist를 음의 무한대로 한다. 만약 N까지 가는 길에 이 사이클이 포함된다면, 결국 dist[N] 또한 음의 무한대가 될 것이다.

입력을 받을 때 cost를 반대로 (금품을 줍는 경우 음수, 빼앗기는 경우 양수) 받았다.

코드

#include <bits/stdc++.h>

using namespace std;

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

void solve() {
    fill(dist, dist+MAX, INF);
    dist[1] = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 1; j < N+1; j++) {
            for (auto p : adj[j]) {
                if (dist[j] != INF && dist[p.first] > dist[j] + p.second) {
                    dist[p.first] = dist[j] + p.second;
                    pnode[p.first] = j;
                    if (i == N-1) {
                        dist[p.first] = -INF;
                    }
                }
            }
        }
    }
    // N까지 가는 길이 존재하지 않는 경우 || N까지 가는 길에 사이클이 존재하는 경우
    if (dist[N] == INF || dist[N] == -INF) cout << -1;
    else {
        int x = N;
        vector<int> v;
        while (x != 0) {
            v.push_back(x);
            x = pnode[x];
        }
        for (auto i = v.rbegin(); i != v.rend(); i++) {
            cout << *i << ' ';
        }
    }
    return;
}

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;
}

여담

그래프 전체에서 사이클이 존재하는지 여부를 판단하는게 아니라 목적지까지 도달하는 경로에 사이클이 존재하는지 여부를 판단할 때 이렇게 풀도록 하자.
그리고 도시 번호 sort해서 출력하는건줄 알았는데 아니었음. 내 두시간..