BOJ 11657 타임머신

• 문제 설명

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

11657번: 타임머신

---

• 문제 풀이

벨만 포드 알고리즘 문제입니다. 

https://jioneprogstdy.tistory.com/32

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

다만 주의할 점이 있는데, 무한 루프가 없을 때 가능한 최단 경로의 최댓값은 (정점 수-1) * (최대거리 값) 이므로 4byte 정수형 값의 범위 안에 속합니다.

그러나 위 문제에서는 모든 간선이 -10000을 가지고 있다면 N번 루프 안에서의 계산의 절대값이 4byte 정수형 값을 넘겨 오버플로우가 발생할 가능성이 있습니다. 따라서 안전하게 8byte 정수형 값을 사용해야합니다.

---

• 소스 코드

#include <bits/stdc++.h>
using namespace std;

vector<pair<int, int>> v[501];
long long dist[501];
long long INF = 1e18;
int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    int n, m;
    int a, b, c;
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        cin >> a >> b >> c;
        v[a].push_back({b, c});
    }
    bool minusCycle = false;
    fill(dist, dist + n + 1, INF);
    dist[1] = 0;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            for (auto &it : v[j])
            {
                if (dist[j] != INF && dist[it.first] > it.second + dist[j])
                {
                    dist[it.first] = it.second + dist[j];
                    if (i == n)
                        minusCycle = true;
                }
            }
        }
    }
    if (minusCycle)
        cout << -1;
    else
    {
        for (int i = 2; i <= n; i++)
        {
            dist[i] != INF ? cout << dist[i] <<'\n' : cout << -1 << '\n';
        }
    }

    return 0;
}