#1954 운동(C++)

문제 링크 : www.acmicpc.net/problem/1956

1956번: 운동

문제풀이는 다음과 같다. 

 

1. 모든 도로의 값에 int형 최대값을 삽입한다.

2. 값을 입력 받는다. 

3. Floyd-Warshall 알고리즘을 통해 각 간선들끼리 이동값의 최소값을 구한다.

4. 2중 for문을 통해 각 간선들을 왕복하는데 걸리는 최소값을 구한다.

 

중요한 것은 도로 값의 초기화를 int형의 최대값으로 해줘야 한다는 점이며, 

이 문제는 반드시 1번지점부터 운동을 시작하지 않아도 된다는 점이다.

 

#include <iostream>
#include <algorithm>

using namespace std;

int v=0, e=0, ans[401][401], res=987654321;

void floyd(){
   for(int k=1; k<=v; ++k){ // 거쳐가는 꼭지점 
      for(int i=1; i<=v; ++i){ // 출발 꼭지점 
         for(int j=1; j<=v; ++j){ // 도착 꼭지점
            ans[i][j] = min(ans[i][j],ans[i][k]+ans[k][j]);
         }
      }
   }
}

int main(void) {
   ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
   int a=0, b=0, c=0;
   cin >> v >> e;
   for(int i=1; i<=v; i++){
      for(int j=1; j<=v; j++){
         ans[i][j] = res;
      }
   }
   for(int i=0; i<e; i++){
      cin >> a >> b >> c;
      ans[a][b] = c;
   }
   floyd();
   for(int i=1; i<=v; i++){
      for(int j=1; j<=v; j++){
         if(i==j) continue;
         res = min(res,ans[i][j]+ans[j][i]);
      }
   }
   if(res==987654321) cout << -1 << "\n";
   else cout << res << "\n";
   return 0;
}