BOJ 11657 - 타임머신

www.acmicpc.net/problem/11657

11657번: 타임머신

 

 

이 문제는 벨만 포드 알고리즘을 이용하여 노드간 최단 거리를 구하는 문제이다.

 

- 참고

: blog.naver.com/kks227/220796963742

벨만 포드 알고리즘(Bellman-Ford Algorithm) (수정: 2020-07-10)

 

위 블로그에 충분히 잘 설명되어 있듯이, 이 문제의 핵심은 벨만 포드 알고리즘에서 음의 사이클이 존재하는지 여부만 파악해서 있으면 -1 을 출력해주는것이 이 문제의 핵심이다.

음의 사이클이 없는 그래프에서, V - 1 만큼 반복문을 돌리면, 문제 없이 최단거리를 구할 수 있으나, 음의 사이클이 존재하면 V - 1 보다 더 많이 반복문을 돌릴경우, 최단 거리가 갱신된다

이는 곧 음의 사이클을 판별하기 위한, 방법이 V - 1 보다 더 많은 반복문을 돌려보는 것이고, 여기서는 V 번 반복문을 돌려서 마지막 V 번째에 최단거리가 갱신된다면, 음의 사이클이 존재한다는 의미가 되므로 이때만 캡쳐해내서, -1 로 출력해주면 된다.

 

 

 

- c++

#include <algorithm>
#include <iostream>
#include <vector>
 
#define INF 1e18
 
using namespace std;
 
int n, m; 
long long dist[500];
vector<pair<int, int>> adj[500];
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> n >> m;
    
    for (int i = 0; i < m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a - 1].push_back({b - 1, c});
    }
    
    bool minus_cycle = false;
    fill(dist, dist + n, INF);
    dist[0] = 0;
    
    for (int i = 0; i < n; ++i) { // 본래 n - 1 만큼 순회하지만, 하나 더 추가한것은 음의 사이클을 체크하기 위함임
        for (int j = 0; j < n; ++j) {
            for (int k = 0; k < adj[j].size(); ++k) {
                int next = adj[j][k].first, d = adj[j][k].second;
                if (dist[j] != INF && dist[next] > dist[j] + d) {
                    dist[next] = dist[j] + d;
                    if (i == n - 1) minus_cycle = true; // n 번째 루프에서 값이 갱신되면, 음의 사이클이 존재
                }
            }
        }
    }
    
    if (minus_cycle) cout << "-1\n";
    else {
        for (int i = 1; i < n; ++i) {
            if (dist[i] != INF) {
                cout << dist[i] << "\n";
            } else {
                cout << "-1\n";
            }
        }    
    }
    
    return 0;
}