(1956) 운동

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

단계별로 풀어보기

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

 

 

 

정점 a와 b를 지나는 사이클 경로는 a에서 b까지 가는 경로와 b에서 a까지 가는 경로를 합친 것으로 생각할 수 있다.

이를 모든 정점 쌍에 대해 수행한 뒤 최솟값을 출력하면 된다.

 

 

 

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int v, k, ans= INF;
  
  cin >> v >> k;
  
  vector dist(v+1, vector<int> (v+1, INF));
  
  while(k--){
    int a, b, c;
    
    cin >> a >> b >> c;
    
    dist[a][b]= c;
  }
  
  for(int m=1;m<=v;m++){
    for(int s=1;s<=v;s++){
      for(int e=1;e<=v;e++){
        dist[s][e]= min(dist[s][e], dist[s][m]+dist[m][e]);
      }
    }
  }
  
  for(int i=1;i<=v;i++){
    for(int j=i+1;j<=v;j++){
      ans= min(ans, dist[i][j]+dist[j][i]);
    }
  }
  
  cout << (ans==INF ? -1 : ans);
  
  return 0;
}