[백준]11657 타임머신 - C++

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

11657번: 타임머신

문제

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다.

1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. 

출력

만약 1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래 전으로 되돌릴 수 있다면 첫째 줄에 -1을 출력한다. 그렇지 않다면 N-1개 줄에 걸쳐 각 줄에 1번 도시에서 출발해 2번 도시, 3번 도시, ..., N번 도시로 가는 가장 빠른 시간을 순서대로 출력한다. 만약 해당 도시로 가는 경로가 없다면 대신 -1을 출력한다.

---

한 지점에서 다른 모든 지점으로 가는 거리 + 음수 간선의 경우 벨만 포드 알고리즘을 활용해야한다.

다만 최악의 상황을 가정했을 때 간선이 6000개, 모든 비용이 -10000 이면 6천만 씩 매 루프마다 감소하므로 -1  * (500-1) * 6천만으로 언더플로우가 나게 되어 dist 배열의 타입을 long long으로 해주어야 한다.

 

#include <iostream>
#include <vector>
#define INF 987654321

using namespace std;
int N,M,a,b,c;
vector<pair<pair<int, int>, int> > edge;
long long dist[510];
long long from,to,cost;

bool bellmanFord(){
    for(int k = 1 ; k <= N - 1;k++){
        for(int i = 0 ; i < edge.size() ; i++){
            from = edge[i].first.first;
            to = edge[i].first.second;
            cost = edge[i].second;
            if(dist[from] != INF){
                if(dist[to] > dist[from] + cost)
                    dist[to] = dist[from] + cost;
            }
        }
    }

    for(int i = 0 ; i < edge.size() ;i++){
        from = edge[i].first.first;
        to = edge[i].first.second;
        cost = edge[i].second;
        if(dist[from] != INF){
            if(dist[to] > dist[from] + cost)
                return false;
        }
    }
    return true;
}

int main (){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> N >> M;
    for(int i = 0 ; i < M ;i++){
        cin >> a >> b >> c;
        edge.push_back(make_pair(make_pair(a,b),c));
    }
    dist[1] = 0;
    for(int i = 2 ; i <= N ; i++){
        dist[i] = INF;
    }

    if(!bellmanFord()){
        cout << -1;
    }
    else{
        for(int i = 2 ; i <= N ; i++){
            if(dist[i] != INF){
                cout << dist[i] << "\n";
            }
            else{
                cout << -1 << "\n";
            }
        }
    }

}

---

문제를 보았을 때 음수 간선 사이클 확인을 해야겠다는 것은 알았지만 막상 하려고 하니 어떻게 해야 하는지 알지 못했다. 음수 간선 사이클에 대해 알기만 하고 실제로 문제를 풀어본 적이 없던가 아니면 옛날에 풀어서 까먹었나 보다. 그래도 이번 기회로 다음에 음수 간선이 나온다면 잘 풀어낼 수 있을 것 같다!