[백준] 11657번 타임머신

전형적인 다익스트라 알고리즘인가 했는데 다익스트라는 양의 가중치일 때만 적용되므로

벨만포드 알고리즘을 수행했다.

 

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

int n,m,a,b,c;
long long dist[501];
bool cycle;
vector<pair<int,int>> v[501];
int main(){
    cin>>n>>m;
    for(int i=0; i<m; i++){
        cin>>a>>b>>c;
        v[a].push_back({b,c}); //v[a]에는 여러 간선 존재!
    }
    for(int i=1; i<=n; i++){
        dist[i] = INF; //모두 INF로 세팅
    }
    dist[1] = 0;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
        {
            for(int k=0; k<v[j].size(); k++){
                int next = v[j][k].first;
                int d = v[j][k].second;
                
                if(dist[j] != INF && dist[next]>dist[j]+d)
                {
                    dist[next] = dist[j]+d;
                    if(i==n) cycle = true;
                }
            }
        }
    if(cycle) cout<<-1<<'\n';
    else{
        for(int i=2; i<=n; i++){
            cout<<(dist[i] !=INF ? dist[i]:-1) <<'\n';
        }
    }
}

- C++에서 int의 최대는 21억이다 (INF)
- if(i==n) cycle = true: 

n번째 반복에서도 최단 거리 갱신이 일어난다면 음수 사이클이 존재한다.

벨만-포드 알고리즘: 노드 개수(n) - 1번 반복하면 모든 최단 거리가 확정됨

 

<참고>

https://cocoon1787.tistory.com/438