BOJ 백준 11657 : 타임머신

시작하면서

　이번 문제는 벨만 포드 알고리즘(Bellman-Ford Algorithm) 을 사용해 해결하는 문제이다.

BOJ 11657 - 타임머신

​

문제 이해

​ 이 문제는 이전에 풀었던 웜홀 문제와 동일한 벨만 포드 알고리즘 문제이다. 문제를 해결하는 방법은 동일하고, 엣지 케이스만 설명하겠다.

1. 버스 노선의 최소,최대 시간이 -10,000~10,000이고, 노선의 개수가 최대 6,000이므로 int_32 자료형을 사용하면 오버플로우가 발생할 수 있다.
2. 만약 음의 사이클이 존재하는 경우가 있다고 해도, 시작점에서 해당 사이클에 접근하는 경로가 없으면 음의 사이클이 아니다.

​

해결

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

#define MAX 99999999

class EdgeInfo
{
public:
    int destination, time;
};

vector<long long> GetBellmanFord(const vector<vector<EdgeInfo>>& edgeInfoVector)
{
    vector<long long> result;
    result.assign(edgeInfoVector.size(), MAX);

    result[1] = 0;

    for (int loop = 0; loop < edgeInfoVector.size() - 1; loop++)
    {
        for (int i = 1; i < edgeInfoVector.size(); i++)
        {
            for (int j = 0; j < edgeInfoVector[i].size(); j++)
            {
                if (result[i] == MAX)
                {
                    continue;
                }

                int destination = edgeInfoVector[i][j].destination;
                int time = edgeInfoVector[i][j].time;
                long long sumOfTime = result[i] + time;

                if (result[destination] > sumOfTime)
                {
                    result[destination] = sumOfTime;
                }
            }
        }
    }

    for (int i = 1; i < edgeInfoVector.size(); i++)
    {
        for (int j = 0; j < edgeInfoVector[i].size(); j++)
        {
            if (result[i] == MAX)
            {
                continue;
            }

            int destination = edgeInfoVector[i][j].destination;
            int time = edgeInfoVector[i][j].time;
            long long sumOfTime = result[i] + time;

            if (result[destination] > sumOfTime)
            {
                result.clear();
                return result;
            }
        }
    }

    for (int i = 2; i < result.size(); i++)
    {
        if (result[i] == MAX)
        {
            result[i] = -1;
        }
    }

    return result;
}

int main()
{
    // sync off
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // sync off

    vector<vector<EdgeInfo>> edgeInfoVector;
    int N, M;

    cin >> N >> M;

    edgeInfoVector.resize(N + 1);
    for (int i = 0; i < M; i++)
    {
        int start, destination, time;
        cin >> start >> destination >> time;

        edgeInfoVector[start].push_back({ destination, time });
    }

    vector<long long> result = GetBellmanFord(edgeInfoVector);
    if (result.empty() == true)
    {
        cout << "-1";
    }
    else
    {
        for (int i = 2; i < result.size(); i++)
        {
            cout << result[i] << "\n";
        }
    }

    return 0;
}