백준 11657 타임머신 C++

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

벨만 포드 알고리즘을 사용하는 문제는 음수 가중치를 가지고 무언가를 하는 문제들인데, 거리 / 비용을 음수로 주기는 표현이 애매하기 때문에 이 문제에서처럼 시간을 가지고 문제를 만드는 것 같다. 웜홀, 시간 여행 등의 주제로 나오는 것 같다.

초기에 간선들의 정보를 받아주고, 다익스트라와 동일하게 모든 정점으로 가는 비용을 무한대로 초기화 한다.

그리고 n-1번에 거쳐서, 모든 정점들의 모든 간선들을 탐색해주고, 마지막 한 번은 음수 사이클 검사용으로 탐색해준다.

마지막 1번의 검색에서, 즉 가장 바깥 루프의 n번째 탐색시에, 경로 / 비용의 갱신이 발생한다면, 이 그래프는 음수 사이클을 포함하고 있다는 의미이다.

그렇지 않으면, 당연히 n개의 정점을 최소비용으로 이동하는 데에 n-1개의 간선이면 충분하기 때문이다.

n-1개 이상 간선을 사용한다는 것은? 어딘가에 음수 사이클이 있기 때문에 계속 그곳을 지나가게끔 갱신이 발생되고 있다는 의미이다.

#include<iostream>
#include<limits.h>
#include<utility>
#include<vector>
using namespace std;
 
typedef pair<int, int> pii;
vector<pii> v[501]; //비용, 목적지
int n, m, dis[501];
bool hasNegativeCycle = false;
void bellmanFord(int st) {
    dis[st] = 0;
    
    for (int t = 0; t < n; t++) { //n-1번 수행하고 +1번은 음수 사이클 확인용
        for (int i = 1; i <= n; i++) { //모든 정점의 간선을 확인하는 것을
            for (int j = 0; j < v[i].size(); j++) {
                int moveCost = v[i][j].first;
                int dst = v[i][j].second;
                if (dis[i] != INT_MAX && dis[dst] > dis[i] + moveCost) {
                    dis[dst] = dis[i] + moveCost;
                    if (t == n-1) hasNegativeCycle = true;
                }
            }
        }
    }
}
int main(void) {
    //ios::sync_with_stdio(false);
    cin.tie(0);
 
    //도시 n개, 엣지 m개
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int from, to, cost;
        cin >> from >> to >> cost;
        v[from].push_back({ cost, to });
    }
    
    //음수사이클 -> -1, 아니면 1번부터 각 노드까지 거리
    for (int i = 1; i <= n; i++)
        dis[i] = INT_MAX;
    bellmanFord(1);
    if (hasNegativeCycle) cout << -1 << '\n';
    else {
        for (int i = 2; i <= n; i++) {
            if (dis[i] != INT_MAX)
                cout << dis[i] << '\n';
            else
                cout << -1 << '\n';
        }
    }
    return 0;
}