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

문제

11657번: 타임머신 (acmicpc.net)

11657번: 타임머신

 

 

풀이

1번 노드에서 시작해서 각 노드까지의 최단거리를 구하는 문제입니다.
하지만 음의 가중치를 갖는 간선이 있기 때문에 다익스트라 대신 벨만-포드 알고리즘을 활용해야 합니다.

 

 

벨만-포드 알고리즘을 이용하여 음수 사이클이 발생하는지 검사한 후 음수 사이클이 발생한다면 -1을 아니라면 각 도시의 최단 경로를 출력해주면 됩니다.

 

 

한 가지 주의해야 할 점은 각 도시의 최단 거리를 저장하는 배열의 자료형을 꼭 고려해야 합니다.

 

 

문제에서 주어진 입력이라면 최대값은 6000 * 10000이라 문제가 되지 않을 것이라고 생각했었는데 '출력초과'라며 통과되지 못했습니다.

 

 

다익스트라에서 처럼 최대값만을 고려하는 것이 아닌

벨만-포드 알고리즘도 최단거리를 구하는 알고리즘이기에 각 노드까지의 거리를 저장하는 배열에는 항상 최소값을 저장하기 때문에 매 반복마다 한없이 작아질 수 있습니다.

최소값은 노드의 개수 * 간선의 개수 * 가중치의 최소값 = 500 * 6000 * -10000이 되고 int32로는 처리할 수 없습니다.

v-1번 반복 후 음수 사이클을 검사하기 위해 한 번 더 반복합니다.

 

 

코드

#include <iostream>
#include <vector>

// 간선의 가중치가 음수인 경우 반복하는 동안 한없이 작아질 수 있다.
#define MAXNUM INT64_MAX 

using namespace std;

struct Edge
{
    int from;
    int dest;
    int weight;
};


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

    int n, m;
    vector<Edge> edges;
    vector<int64_t> dist;

    cin >> n >> m;
    edges.reserve(m);
    dist.assign(n+1, MAXNUM);

    for (int i=0; i<m; ++i)
    {
        int dest, from, weight;
        cin >> from >> dest >> weight;
        edges.push_back({from, dest, weight});
    }

    dist[1] = 0;
    for (int i=1; i<n+1; ++i)
    {
        for (Edge e : edges)
        {
            int from = e.from;
            int dest = e.dest;
            int weight = e.weight;

            if (dist[from] == MAXNUM)
                continue;

            if (dist[dest] > dist[from] + weight)
                dist[dest] = dist[from] + weight;
        }
    }

    vector<int64_t> answer = dist;

    // 음의 사이클 검사
    for (Edge e : edges)
    {
        int from = e.from;
        int dest = e.dest;
        int weight = e.weight;

        if (dist[from] == MAXNUM)
            continue;

        if (dist[dest] > dist[from] + weight)
            dist[dest] = dist[from] + weight;
    }

    // 출력을 위한 코드
    bool isCycle = false;
    for  (int i=1; i<n; ++i)
    {
        if (answer[i] != dist[i])
        {
            isCycle = true;
            break;
        }
    }

    if (isCycle)
        cout << -1 << "\n";
    else
    {
        for (int i=2; i<n+1; ++i)
        {
            int d = answer[i];
            if(d == MAXNUM)
                cout << -1 << "\n";

            else
                cout << d << "\n";
        }
    }

    return 0;
}