[백준] 1738번 골목길

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define INF 1e18
using namespace std;

int n,m;
vector<pair<int,long long>> adj[101];
long long dist[101];
int pnode[101];

void solve(){
    for(int i=0; i<101; i++){
        dist[i]=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;
                    }
                }
            }
        }
    if(dist[n] == INF || dist[n] == -INF) cout<<-1; //n까지 가는 길이 없음
    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(){
    fastio;
    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;
}

<참고>

https://velog.io/@ks1ksi/%EB%B0%B1%EC%A4%80-1738%EB%B2%88-%EA%B3%A8%EB%AA%A9%EA%B8%B8

<풀이>

dist[i]: 1번 도시부터 i번 도시까지 최대 거리

pnode[i]:i로 오기 직전의 노드

[1]

if(i == n - 1) {

     dist[p.first] = -INF;  // 

}

n번째 반복 시 갱신된 노드는 사이클 포함이므로 무효화

 

[2]

while(x != 0) {

      v.push_back(x);

      x = pnode[x];  

}

: 경로 역추적 ex) 1->2->4 라면 pnode[2]=1, pnode[4]=2 일 것

이후 v.rbegin()으로 출력은 역순으로 수행함

[3]

INF = 1e18 : long long 범위 안에서 충분히 큰 수, 오버플로우 방지용

i는 총 반복 횟수

벨만-포드는 n - 1만큼 반복하면 최단거리 갱신이 끝나야 함

i==n-1일 때는 음수 사이클 있는지 확인하는 반복임