[Bellman-Ford]BOJ 11657_타임머신

문제 링크 : www.acmicpc.net/problem/11657

11657번: 타임머신

벨만-포드 알고리즘을 이해하고 연습해볼 수 있는 문제이다.

벨만-포드 알고리즘에 대해서는 다음 포스트를 참조하자.

벨만-포드 알고리즘(Bellman-Ford Algorithm)

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
 
#define INF 999999999999
 
using namespace std;
typedef pair<int, int> p;
 
vector<p> adj[500];
int n, m;
long long dist[500];
bool cycle = false;
 
void bellman() {
    for (int i = 0; i < n; i++) {
        //i번 노드를 기준으로 반복
        for (int j = 0; j < n; j++) {
            //현재 보고 있는 j번 노드가 i번 노드 기준으로 도달할 수 있을 때만 비교
            if (dist[j] == INF) continue;
 
            //j번 노드의 인접 리스트를 참조
            for (int k = 0; k < adj[j].size(); k++) {
                p temp = adj[j][k];
                if (dist[temp.first] > dist[j] + temp.second) {
                    //더 짧은 거리일 경우 갱신
                    dist[temp.first] = dist[j] + temp.second;
                    if (i == n - 1) cycle = true;
                }
            }
        }
    }
}
 
void init() {
    int a, b, c;
    cin >> n >> m;
    
    for (int i = 0; i < m; i++) {
        cin >> a >> b >> c;
        adj[a - 1].push_back({ b - 1, c });
    }
 
    fill(dist, dist + n, INF);
    dist[0] = 0;
}
 
int main() {
    init();
 
    bellman();
 
    if (cycle) {
        printf("-1\n");
        return 0;
    }
 
    for (int i = 1; i < n; i++) {
        if (dist[i] == INF) printf("-1\n");
        else printf("%lld\n", dist[i]);
    }
 
    return 0;
}
 

음의 사이클을 확인하기 위해 16번째 줄에서 총 n번의 iteration을 진행한다.

마지막 n번째의 iteration에 dist값 변화가 발생한다면, 음의 사이클이 존재한다는 것이다.