타임머신.md

DONE_DATE	2025/01/16

타임머신

난이도

• 골드 4

문제

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

알고리즘 분류

• 그래프 이론
• 최단 경로
• 벨만–포드

정답코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> Edge; // weight, vertex
typedef vector<vector<Edge>> Graph;

bool bellmanFord(int start, Graph &graph, vector<ll> &dist) {
    dist[start] = 0;
    for (int i = 0; i < graph.size() - 1; i++) {
        for (int u = 0; u < graph.size(); u++) {
            for (auto &edge: graph[u]) {
                auto [w, v] = edge;
                if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                }
            }
        }
    }

    for (int u = 0; u < graph.size(); u++) {
        for (auto &edge: graph[u]) {
            auto [w, v] = edge;
            if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
                return false;
            }
        }
    }

    return true;
}

int main() {
    int n, m;
    cin >> n >> m;

    Graph graph(n + 1);

    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].emplace_back(c, b);
    }

    vector<ll> dist(n + 1, INT_MAX);
    if (!bellmanFord(1, graph, dist)) {
        cout << -1;
        return 0;
    }
    for (int i = 2; i < n + 1; i++) {
        cout << (dist[i] == INT_MAX ? -1 : dist[i]) << '\n';
    }
}

회고

• 처음으로 풀어본 벨만포드 알고리즘이다.
• 벨만포드 알고리즘은 다익스트라 알고리즘과 다르게 음수 가중치가 있어도 사용할 수 있다.
• 벨만포드 알고리즘은 간선을 n-1번 순회하면서 각 정점까지의 최단 거리를 갱신한다.
• 시간복잡도는 O(VE)이다.
• 벨만포드 알고리즘은 음수 사이클이 존재하는지 확인할 수 있다. 음수 사이클이 존재하면 최단 거리를 구할 수 없다. 그 경우 -1을 출력하면 된다.
• 도달할 수 없는 정점은 -1을 출력하면 된다.
• 처음 풀때 출력초과가 나왔는데 이거는 dist 배열을 int로 선언해서 발생한 문제였다. long long으로 바꿔주니 해결되었다.
• 사실 질문게시판에
  500개 vertex, 6,000개의 edge가 -10,000 일 경우 최솟값 계산이기에 -30억이 나올 수 있습니다. 양수로는 최대 60,000,000까지만 가능해서 INF값 설정을 작게 잡아도 되지만, dis를 저장하는 배열은 long long으로 선언해야 INT 음수 최댓값 범위 바깥을 커버할 수 있습니다.
• 라고 해서 수정했다.