BOJ 11657번 : 타임머신

그래프로 표현했을 때 간선이 음수의 값을 가지고, cycle을 찾아내야 하므로 벨만-포드 알고리즘을 사용해야 한다.

https://00rigin.tistory.com/57

벨만포드 알고리즘

 

<소스코드>

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
 
using namespace std;
 
int N,M;
vector<pair<int,int>> v[501];
vector<long long> d;
 
bool cir = false; // cycle 표시용
 
void bell(int s){
    
    d[s] = 0;
    
    for(int i = 1; i<=N; i++){ // i == N(노드 갯수) 까지 오면 cycle을 돌고 있는 것!
        for(int j = 1; j<=N; j++){ // 각 노드를 방문하여 탐색 
            for(auto &n : v[j]){
                if(d[j] == LONG_LONG_MAX) continue; // 한번 방문했던 노드만
                if(d[n.first] > n.second + d[j]){
                    d[n.first] = n.second + d[j];
                    if(i == N){
                        cir = true;
                        
                    }
                }
                
            }
        }
    }
    
    
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    cin>>N>>M;
    
    for(int i = 1; i<=M; i++){
        int a,b,c;
        cin>>a>>b>>c;
        
        v[a].push_back(make_pair(b,c));
        
    }
    
    for(int i = 0; i<=N+1; i++){
        d.push_back(LONG_LONG_MAX);
    }
    
    bell(1);
    
    if(cir == true){
        cout<<"-1"<<endl;
    }
    else{
        for(int i = 2; i <=N; i++){
            if(d[i] == LONG_LONG_MAX)
                cout<<"-1"<<endl;
            else
                cout<<d[i]<<endl;
        }
    }
    
    
    
}
 

 

<문제>

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

11657번: 타임머신