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

백준의 타임머신(11657) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 1번 도시에서 나머지 도시로 갈 때 걸리는 최단시간을 구해야 하는 문제이다.

   즉, 최소비용을 구하면 되는 문제이기 때문에 접근방법으로 다익스트라 알고리즘이나 벨만포드 알고리즘을 생각해볼 수

   있다.

   그런데 ! 가는데 걸리는 시간이 음수가 존재하는 문제이다. 즉, 양의 가중치가 있을 때만 적용시킬 수 있는 다익스트라

   알고리즘으로는 풀 수가 없는 문제이다. 따라서, 벨만포드 알고리즘을 사용하면 해결할 수 있는 문제이다.

   문제에서 출력에 적혀 있는 부분에 보면, '시간을 무한히 오래전으로 되돌릴 수 있다면 -1을 출력' 하라는 말이 있다.

   이 말은, '음의 사이클이 존재하는 그래프라면, -1을 출력하라' 라는 말과 같다.

   왜냐하면, 음의 사이클이 존재하게 되면, 특정 노드에 가는데 걸리는 시간을 무한히 작게 만들 수 있기 때문이다.

   이 문제는 벨만포드 알고리즘만 알고 있다면 구현에 큰 어려움이 없을 문제라 생각해서, 구체적인 풀이방법 대신,

   벨만포드 알고리즘을 설명한 글로 설명을 대체하겠다.

   [ 벨만 포드 알고리즘 알아보기 (Click) ]

2) 재채점 되는 과정에서 맞았습니다에서 결과가 출력초과로 바뀌게 되어서 확인해봤더니,

   입력이 다음과 같이 주어지는 경우가 있는 것 같다.

   N = 500 이고, M = 6000 일 때, 6000개의 간선이

   1 → 2 로 -10000 만큼의 비용이 든다.

   2 → 1 로 -10000 만큼의 비용이 든다.

   이 2개로만 6000개가 채워지는 입력이 있는 것 같습니다.

   위의 경우는 당연하게 음의사이클이 발생함에도, 그 음의사이클의 수치가 int형의 범위를 넘어서서 음의 사이클이

   발생하지 않는다고 판단되는 문제가 있어서, 자료형을 long long을 이용해서 구현해주었습니다.

  

[ 소스코드 ]

#include<iostream>
#include<vector>
 
#define endl "\n"
#define MAX 510
#define INF 987654321
using namespace std;
 
int N, M;
long long Dist[MAX];
vector<pair<pair<int, int>, int>> Edge;
 
void Input()
{
    cin >> N >> M;
    for (int i = 1; i <= N; i++) Dist[i] = INF;
    for (int i = 0; i < M; i++)
    {
        int From, To, Cost;
        cin >> From >> To >> Cost;
        Edge.push_back(make_pair(make_pair(From, To), Cost));
    }
}
 
void Solution()
{
    Dist[1] = 0;
    for (int i = 1; i <= N - 1; i++)
    {
        for (int j = 0; j < Edge.size(); j++)
        {
            int From = Edge[j].first.first;
            int To = Edge[j].first.second;
            int Cost = Edge[j].second;
 
            if (Dist[From] == INF) continue;
 
            if (Dist[To] > Dist[From] + Cost) Dist[To] = Dist[From] + Cost;
        }
    }
 
    for (int i = 0; i < Edge.size(); i++)
    {
        int From = Edge[i].first.first;
        int To = Edge[i].first.second;
        int Cost = Edge[i].second;
 
        if (Dist[From] == INF) continue;
        if (Dist[To] > Dist[From] + Cost)
        {
            cout << -1 << endl;
            return;
        }
    }
 
    for (int i = 2; i <= N; i++)
    {
        if (Dist[i] == INF) cout << -1 << endl;
        else cout << Dist[i] << endl;
    }
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}

cs