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

백준

https://www.acmicpc.net/problem/11657

풀이

[벨만-포드 알고리즘]

음의 간선이 있기 때문에 다익스트라가 아닌 벨만-포드 알고리즘을 사용하자

플로이드 와샬도 가능은 할 것 같은데 일단 벨만-포드를 사용했다

 

Bellman-Ford algorithm

모든 노드를 돌면서

to 노드로 이동하는 것이 Dist[to]보다 저렴하면 갱신한다.

이것을 (노드수-1번) 반복한다.

 

check negative weight cycles

한 번 더 이동하는데 값이 작아지면

음의 가중치 사이클이 있는 것이다.

코드

#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;
#define INF 20000000

int main()
{
    int N, M; cin >> N >> M;

    vector<long long> Dist(N + 1, INF);
    Dist[1] = 0;

    vector<vector<pair<int, int>>> graph(N + 1);

    // INPUT
    for (int i = 0; i < M; i++)
    {
        int start, goal, time;
        cin >> start >> goal >> time;
        graph[start].push_back({ goal, time });
    }

    // Bellman-Ford Algorithm
    for (int i = 1; i <= N - 1; i++)
    {
        for (int from = 1; from <= N; from++)
        {
            for (auto edge : graph[from])
            {
                int to = edge.first;
                int time = edge.second;

                if (Dist[from] != INF && Dist[to] > Dist[from] + time)
                {
                    Dist[to] = Dist[from] + time;
                }
            }
        }
    }

    // Check negative weight cycles
    for (int from = 1; from <= N; from++)
    {
        for (auto edge : graph[from])
        {
            int to = edge.first;
            int time = edge.second;

            if (Dist[from] != INF && Dist[to] > Dist[from] + time)
            {
                cout << "-1" << endl;
                return 0;
            }
        }
    }

    // RESULT
    for (int i = 2; i <= N; i++)
    {
        if (Dist[i] == INF)
            cout << "-1" << endl;//cant go
        else
            cout << Dist[i] << endl;//can go
    }

    return 0;
}

 

다익스트라랑 플로이드와샬 알고리즘 공부하면서

벨만 포드도 공부해야겠다 했는데

문제로 먼저 만났다

어 이거 벨만-포드 쓰는거다 라고 생각이 들었는데 구현은 몬했다ㅋㅋㅋㅋ