[BOJ/C++] 11657 타임머신

시작 노드에서 다른 모든 노드까지의 최단거리를 구하며

가중치가 음수도 가능하기 때문에 벨만-포드 알고리즘을 이용해 문제를 해결할 수 있습니다.

벨만-포드 알고리즘 수행 과정

1. 모든 에지와 관련된 정보를가져온 후 다음 조건에 따라 최단 거리 배열을 업데이트

   if(dist[start]!=INT_MAX && dist[arrive] > 	dist[start] + weight)
   	dist[arrive] = dist[start] + weight;

2. 노드 개수 -1 만큼 1번을 반복
3. 음수 사이클의 유무를 확인하기 위해 1번 수행
   • 이 때 한번이라도 업데이트 된다면 음수사이클이 발생한다고 판단

distance 배열을 int로 했더니 출력 초과가 발생했습니다.

그 이유는 벨만-포드 알고리즘의 경우 음수 사이클에서 계속해서 최솟값으로 갱신하다보면 언더플로우가 발생할 수 있습니다.

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <string>
#include <climits>

using namespace std;

using int32 = long;
using int64 = long long;

using Edge = tuple<int, int, int>;

static vector<Edge> G;
static vector<int64> dist;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N, M;
    cin >> N >> M;

    dist.resize(N + 1, INT64_MAX);

    for(int i=0; i<M; i++)
    {
        int start, arrive, weight;
        cin >> start >> arrive >> weight;

        G.emplace_back(start, arrive, weight);
    }

    dist[1] = 0;        // satrt node

    for(int i=1; i<N; i++)
    {
		for(int j=0; j<M; j++)
		{
            Edge edge = G[j];
			int start = get<0>(edge);
			int arrive = get<1>(edge);
			int weight = get<2>(edge);
			if (dist[start] != INT64_MAX && dist[arrive] > dist[start] + weight)
			{
				dist[arrive] = dist[start] + weight;
			}
		}
    }
    

    bool bCycle = false;
    // 음수 사이클 확인
    for (int i=0; i<M; i++)
    {

    	Edge edge = G[i];
    	int start = get<0>(edge);
    	int arrive = get<1>(edge);
    	int weight = get<2>(edge);

        if (dist[start] != INT64_MAX && dist[arrive] > dist[start] + weight)
        {
            // 음수 사이클 발생
            bCycle = true;
            break;
        }
            
    }

    if(bCycle)
    {
        cout << -1;
    }
    else
    {
        for (int i = 2; i<=N; i++)
        {
            if (dist[i] == INT64_MAX)
                cout << -1 << '\n';
            else
                cout << dist[i] << '\n';
        }
            
    }


    return 0;
}