[백준OJ] 11657번 타임머신

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

11657번: 타임머신

---

 

-풀이-

벨만 포드알고리즘을 이용하여, 음의 사이클이 존재하면 -1을 출력해주고, 음의 사이클이 존재하지 않는다면, 1번정점을 제외한 다른 정점들까지의 최단거리를 출력하면된다.

 

-시간복잡도-

벨만포드 알고리즘의 시간복잡도는 O(VE) 즉 O(NM)이 된다.

 

-코드-

#include <algorithm>
#include<iostream>
#include<vector>
#define INF 987654321
using namespace std;

typedef pair<pair<int,int>,int> edge;

vector<edge> edges;
long long dist[510];
int n,m;

void bf(){
    for(int i=1;i<=n;i++) dist[i]=INF;
    dist[1]=0;
    
    for(int i=1;i<=n-1;i++){
        for(int j=0;j<edges.size();j++){
            int u,v,t;
            
            u=edges[j].first.first;
            v=edges[j].first.second;
            t=edges[j].second;
            if(dist[u]==INF) continue;
            if(dist[v]>dist[u]+t){
                dist[v]=dist[u]+t;
            }
        }
    }
    
    for(int i=0;i<edges.size();i++){
        int u,v,t;
            
        u=edges[i].first.first;
        v=edges[i].first.second;
        t=edges[i].second;
        
        if(dist[u]==INF) continue;
        if(dist[v]>dist[u]+t){
            cout<<-1<<"\n";
            return;
        }
    }
    
    for(int i=2;i<=n;i++){
        if(dist[i]==INF) cout<<-1<<"\n";
        else cout<<dist[i]<<"\n";
    }
    
    return;
}

int main(){
    cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
    
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        edges.push_back({{a,b},c});
    }
    bf();
    
}