11657번: 타임머신

11657번: 타임머신

사용 언어: C++

 

풀이

음수 간선이 있으므로 벨만포드 알고리즘으로 풀면 된다. 벨만포드는 1번부터 n번 거리 완하를 시도하고, n번째 완하에도 거리가 줄어든다면 무한대로 줄어들 수 있는 경로가 있다는 것이므로 false return 한다.

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

typedef long long ll;
const ll INF = 1e18; // 무한대

int N, M;
ll D[555]; // 거리 배열, 최단 거리를 저장
vector<tuple<int, int, ll>> E; // 간선 목록 {출발지, 도착지, 가중치}

void AddEdge(int s, int e, int w)
{
    E.emplace_back(s, e, w);
}

// 벨만-포드 알고리즘: 음수 사이클이 있으면 false 반환
bool Run(int s)
{
    fill(D, D + N + 1, INF);
    D[s] = 0;

    for (int iter = 1; iter <= N; iter++)
    {
        bool changed = false;
 
        for (auto [u, v, w] : E)
        {
            if (D[u] == INF) continue; // 출발 도시가 무한대라면 건너뜀
            if (D[v] > D[u] + w)
            {
                D[v] = D[u] + w;
                changed = true;
            }
        }

        // N번째 반복에서 간선이 완화되면 음수 사이클이 있음
        if (iter == N && changed)
        {
            return false;
        }
    }

    return true;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N >> M;

    for (int i = 0; i < M; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        AddEdge(a, b, c);
    }

    if (!Run(1))
    {
        cout << "-1\n"; // 음수 사이클이 있으면 -1 출력
    }
    else
    {
        for (int i = 2; i <= N; i++)
        {
            if (D[i] == INF)
            {
                cout << "-1\n"; // i번 도시가 도달 불가능하면 -1 출력
            }
            else
            {
                cout << D[i] << "\n"; // 최단 거리 출력
            }
        }
    }

    return 0;
}