(C++) - 백준(BOJ) 11657번 : 타임머신

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

11657번: 타임머신

벨만포드 문제였습니다.

 

풀이방법

 1. 매번 edge에대해 벨만포드 알고리즘을 수행합니다.

 

 2. 최단경로는 최대 N개의 정점 N-1개의 간선을 가지므로 N번째 수행시 갱신값이 있다면 음수 사이클 판정을 할 수 있습니다.

 

 3. 음수 사이클이 존재한다면 -1만 출력. 아닐 경우에는 1에서 출발해 2 ~ N으로 가는 정점까지의 시간을 출력. 만약 해당 점점으로 가는 방식이 없어 dist배열이 INF라면 -1출력입니다.

Code

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
using namespace std;
using pll = pair<ll,ll>;
ll n, m, w;
vector <pll> graph[505];

int bellmanFord(ll start,ll end,vector<ll> &dist){
    dist[start] = 0;
    for(ll i = 1; i <= end; i++){
        for(ll cur = 1; cur <= end; cur++){
            if(dist[cur] == INF) continue;
            for(auto &el : graph[cur]){
                ll next = el.first;
                ll nextCost = el.second;
                if(dist[next] > dist[cur] + nextCost){
                    dist[next] = dist[cur] + nextCost;
                    if(i == end) return -1; //음수 사이클 발생
                }
            }
        }
    }
    return 1;
}
int main(){
    cin >> n >> m;
    vector<ll> dist(n + 1,INF);

    for(ll i = 0,s,e,t; i < m; i++){
        cin >> s >> e >> t;
        graph[s].push_back({e,t});
    }
    if(bellmanFord(1,n,dist) != -1){
        for(ll i = 2; i <= n; i++) {
            if(dist[i] == INF) cout << -1;
            else cout << dist[i];
            cout << '\n';
        }
    }
    else cout << -1;
}