(11657) 타임머신

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

단계별로 풀어보기

29단계(최단 경로) 5번째

 

 

 

다익스트라는 음의 가중치를 가진 간선이 있으면 사용할 수 없다. 나중에 방문한 경로가 기존 최단 거리보다 짧을 수도 있기 때문이다.

이때 사용할 수 있는 것이 벨먼-포드 알고리즘이다. O(VE)로 시간복잡도는 더 크지만 유연해서 음의 간선이 있어도 사용 가능하다.

또한 음수 사이클이 존재할 때에도 이를 찾아내고 무한 루프를 방지할 수 있다.

 

참고로 다익스트라 알고리즘도 구현 방식에 따라 음의 간선이 있어도 사용 가능하게 만들 수 있다. 하지만 퀵정렬처럼 저격용 데이터가 들어오면 최악의 경우 소요 시간이 엄청나게 커서 PS에서는 쓰기 어렵다. 가지치기 등 각종 분기를 만들면 되겠지만 그럴 바에는 그냥 벨먼-포드 알고리즘을 쓰자.

 

 

 

#include <iostream>
#include <vector>
using namespace std;
#define INF 5000001
typedef pair<pair<int,int>,int> p;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, m;
  
  cin >> n >> m;

  vector<p> adj;
  vector<long> dist(n+1, INF);
  
  while(m--){
    int a, b, c;
    
    cin >> a >> b >> c;
    
    adj.push_back({{a, b}, c});
  }
  
  dist[1]= 0;
  
  for(int i=1;i<n;i++){
    for(p edge:adj){
      int from= edge.first.first;
      int to= edge.first.second;
      int cost= edge.second;
      
      if(dist[from]==INF)  continue;
      
      dist[to]= min(dist[to], dist[from]+cost);
    }
  }
  
  for(p edge:adj){
    int from= edge.first.first;
    int to= edge.first.second;
    int cost= edge.second;
    
    if(dist[from]==INF)  continue;
    
    if(dist[to]>dist[from]+cost){
      cout << -1;
      
      return 0;
    }
  }
  
  for(int i=2;i<=n;i++){
    cout << (dist[i]==INF ? -1 : dist[i]) << "\n";
  }
  
  return 0;
}