[C++] 백준 11657 타임머신

#include <iostream>
#include <vector>
#include <tuple>
 
using namespace std;
#define Max 60000001
 
long long city[501] = {};
vector<tuple<int, int, long long>> vec = {};
 
int main()
{
	int N = 0;
	int M = 0;
	cin >> N >> M;
 
    for (int i = 1; i <= N; ++i)
    {
        city[i] = Max;
    }
 
	while (M--)
	{
		int A = 0;
		int B = 0;
		int C = 0;
		cin >> A >> B >> C;
 
        vec.push_back({ A, B, C });
	}
 
    city[1] = 0;
 
    for (int i = 1; i <= N - 1; ++i)
    {
        for (int j = 0; j < vec.size(); ++j)
        {
            int start = get<0>(vec[j]);
            int end = get<1>(vec[j]);
            long long cost = get<2>(vec[j]);
 
            if (city[start] == Max)
                continue;
 
            if (city[end] > city[start] + cost) 
                city[end] = city[start] + cost;
        }
    }
 
    for (int i = 0; i < vec.size(); ++i)
    {
        int start = get<0>(vec[i]);
        int end = get<1>(vec[i]);
        long long cost = get<2>(vec[i]);
 
        if (city[start] == Max) 
            continue;
 
        if (city[end] > city[start] + cost)
        {
            cout << -1 << "\n";
            return 0;
        }
    }
 
    for (int i = 2; i <= N; i++)
    {
        if (city[i] == Max)
            cout << -1 << "\n";
 
        else 
            cout << city[i] << "\n";
    }
 
	return 0;
}

값에 음수값이 들어가기 때문에 벨만포드 알고리즘을 사용해야 합니다.

N-1번 째를 돌렸을 때 음수사이클이 돌아가는지 확인이 가능하기 때문에 정점의 수 - 1 만큼 회전시킵니다.

마지막으로 확인했을 때 또 줄어든다면 음수사이클이 돌아가기 때문에 -1로 표시합니다

그렇지 않다면 현재 도착하는 수를 표시합니다.