11657. 타임머신

11657. 타임머신

 

 

전형적인 벨만-포드 알고리즘 문제다.

• 음수 가중치가 있을 때, 한 점으로부터 다른 점들까지의 거리를 구한다.
• 음수 사이클을 판별할 때도 사용된다.

 

이 문제는 int를 사용할 경우 오버플로우가 발생해 출력 초과로 틀리게 되므로, long long 자료형을 사용해야 한다.

 

#include <iostream>
#include <vector>
#include <climits>

#define UNREACHABLE LLONG_MAX

using namespace std;

struct Edge
{
    int s;
    int e;
    int w;
};

int main(int argc, char* argv[])
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

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

    vector<Edge> edges;

    while (M--)
    {
        int start, end, time;
        cin >> start >> end >> time;

        edges.push_back({start, end, time});
    }

    vector<long long> cost(N + 1, UNREACHABLE);
    cost[1] = 0;

    while (--N)
    {
        for (Edge& ed : edges)
        {
            long long c = cost[ed.s] + ed.w;

            if (cost[ed.s] != UNREACHABLE && c < cost[ed.e])
                cost[ed.e] = c;
        }
    }

    for (Edge& ed : edges)
    {
        long long c = cost[ed.s] + ed.w;

        if (cost[ed.s] != UNREACHABLE && c < cost[ed.e])
        {
            cout << -1;
            return 0;
        }
    }

    for (int i = 2; i < cost.size(); ++i)
        cout << (cost[i] == UNREACHABLE ? -1 : cost[i]) << endl;

    return 0;
}