Baekjoon 11657번 타임머신

문제

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

걸린 시간

- 실패

풀이

C++

#include <bits/stdc++.h>
#define INF 1e18
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int n, m, a, b, c;
vector<pair<int, int>> adj[501]; // dest, cost

void bellmanFord(){
    vector<ll> upper(n+1, INF);
    upper[1] = 0;
    bool updated;
    for(int iter = 1; iter <= n; iter++){
        updated = false;
        for(int here = 1; here <= n; here++){
            for(int i = 0; i < adj[here].size(); i++){
                int there = adj[here][i].first;
                int cost = adj[here][i].second;
                if(upper[here] != INF && upper[there] > upper[here] + cost){
                    upper[there] = upper[here] + cost;
                    updated = true;
                }
            }
        }
        if(!updated) break;
    }
    if(updated)
        cout << -1 << "\n";
    else
        for(int i = 2; i <= n; i++)
            if(upper[i] == INF) cout << -1 << "\n";
            else cout << upper[i] << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        cin >> a >> b >> c;
        adj[a].push_back(make_pair(b, c));
    }
    bellmanFord();
    return 0;
}

음수 간선이 존재하기 때문에 다익스트라가 아닌 벨만-포드 알고리즘을 사용하여야 한다.

종만북에서 벨만-포드 알고리즘 구현을 보고 문제를 풀었는데 자꾸만 55% 에서 틀렸습니다가 출력되었다.

ac 를 받은 코드와의 차이점은 upper[here] != INF 조건이 추가되었다는 점인데, 이렇게 하면 완화가 반복되어도 가지 못하는 경로의 INF 값은 줄어들지 않아 경로가 존재하는지를 INF 에 적당히 큰 값 M 을 빼어 최단거리와 비교하지 않아도 된다.

그 밖에 가중치의 범위가 -10000 부터 10000 이기 때문에 최악의 경우, 최단거리는 500 * 6000 * -10000 = -3e10 으로 int 자료형을 사용하면 언더플로가 일어난다. long long 자료형을 사용해 주면 해결된다.

참고

벨만 포드 최단경로 알고리즘의 구현 - Bellman-Ford Shortest Path Algorithm