BOJ : 11657 타임머신

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

최단거리를 찾는 문제같은데 타임머신이 있거나 시간을 역행하는 문제, 음수 가중치가 존재하는 대다수의 문제는 벨만-포드 알고리즘으로 해결가능합니다.

다익스트라 알고리즘 같은 경우 해당 노드에 존재하는 간선을 보고 가중치가 가장 작은 값을 선택하게 됩니다.

그렇기 때문에

A -> B -> C / A -> C 의 루트에서

1      5      -4   1      3

의 값을 가질 때 

노드 A의 간선의 가중치 5와 3만을 비교하기 때문에 원하는 답을 도출할 수 없습니다.

왜냐하면 1 -> 5 -> -4이 더 최단 거리가 되기 때문이죠.

그렇기 때문에 간선을 비교하고 또 노드의 개수-1만큼 또 비교를 해주면 됩니다. (도착지 노드까지 가는 간선은 전체 노드개수를 넘지 않기 때문)

하지만 그래프 특성상 사이클이 생길 수도 있는데 음수 값이 들어간다면 음수 값으로 갱신 되는 일이 발생하겠죠.

이를 음수 싸이클 혹은 음의 싸이클(Negative Cycle)이라고 합니다.

해당 문제에서는 음수 싸이클이 발생하면 -1을 출력하라고 하니, N-1까지 돌고 N번째 반복문을 돌 때 값이 갱신되는 부분이 있으면 -1을 출력해주면 됩니다.

#include <cstdio>
#include <vector>
using namespace std;

#define INF 987654321

int main(){
    int N,M;
    int dist[502];
    bool cycle = false;
    vector<pair<int, int>> v[502];
    scanf("%d%d",&N,&M);
    for(int i=0;i<M;i++){
        int A,B,C;
        scanf("%d%d%d",&A,&B,&C);
        v[A].push_back(make_pair(B, C));
    }
    for(int i=1;i<=N;i++)
        dist[i]=INF;
    
    dist[1] = 0;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            for(auto &n : v[j]){
                if(dist[j] != INF && dist[n.first] > n.second + dist[j]){
                    dist[n.first] = n.second + dist[j];
                    if(i == N) cycle = true;
                }
            }
        }
    }
    
    if(cycle) printf("-1\n");
    else{
        for(int i=2;i<=N;i++)
            if(dist[i]==INF) printf("-1\n");
            else printf("%d\n",dist[i]);
    }
    
}