백준 11657 - 타임머신

문제

 

https://www.acmicpc.net/problem/11657

11657번: 타임머신

 

 

풀이

 

벨만-포드 알고리즘을 이용하는 문제이다. 벨만 포드 알고리즘은 가중치에 음수가 있는 경우에서 최단경로를 찾고 싶을 때 사용하는 알고리즘이다. 모든 간선에 대해서 정점의 개수-1 (N-1) 번의 relaxation 과정을 거치면 시작 정점에서부터 최단 경로를 구할 수 있게 된다. 벨만포드는 음의 사이클을 가지지 않는 그래프에서는 최단 경로를 구할 수 있다.

 

문제에서 음의 사이클이 있는지 없는지 알아야 한다. 이때는 모든 간선에 대해서 N번의 relaxation 과정을 하고 N번째에서 최단 경로가 갱신되는지 아닌지 확인을 하면 된다. 만약 음의 사이클이 없다면 N-1번째에서 완성된 최단 경로가 바뀌지 않을 것이고, 만약 음의 사이클이 존재한다면 N번째 과정에서 최단 경로가 갱신이 될 것이다. 

 

 

코드

 

#include <iostream>
#include <vector>
 
using namespace std;
 
const int INF = 987654321;
 
vector< pair<int, int> > edge[501];
int N, M;
int A, B, C;
long long d[501];
bool isNegative;
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
 
    cin >> N >> M;
    for (int i=0; i<M; i++)
    {
        cin >> A >> B >> C;
        edge[A].push_back({B, C});
    }
 
    for (int i=2; i<=N; i++) d[i] = INF;
 
    for (int i=1; i<=N; i++)
    {
        for (int u=1; u<=N; u++)
        {
            for (auto cur : edge[u])
            {
                int v = cur.first;
                int w = cur.second;
 
                if (d[u] != INF && d[v] > d[u] + w) 
                {
                    d[v] = d[u] + w;
                    if (i == N) isNegative = true;
                }
            }
        }
    }
 
    if (isNegative) cout << -1;
    else
    {
        for (int i=2; i<=N; i++)
        {
            if (d[i] == INF) cout << -1 << '\n';
            else cout << d[i] << '\n';
        }
    }
    
    return 0;
}