BOJ #1956 - 운동

https://icpc.me/1956

# 문제 분류
최단 경로 찾기 (Floyd-Warshall Algorithm)

풀이 접근 방법 :

 

1. 마을과 마을 사이를 연결하는 도로는 일방통행 도로이다.

2. 자기 자신의 가중치를 0으로 설정하지 말고 INF로 두어 갱신 가능하게 설정, Floyd-Warshall.

3. 답이 나온다.

---

간단한 문제다. 오히려 회장뽑기@2660 보다 쉽다.

 

#include <iostream>
using namespace std;
 
int INF = 1e9;
int V, E, a, b, c, arr[410][410], minn = INF, cnt;
 
int main(){
    scanf("%d %d",&V,&E);
    for(int i=0; i<410; i++){
        for(int j=0; j<410; j++) arr[i][j] = INF;
    }
    for(int i=0; i<E; i++){
        scanf("%d %d %d", &a, &b ,&c);
        arr[a][b] = c;
    }
    
    for(int i=1; i<=V; i++){
        for(int j=1; j<=V; j++){
            for(int k=1; k<=V; k++){
                arr[j][k] = min(arr[j][k], arr[j][i]+arr[i][k]);
            }
        }
    }
     
    for(int i=1; i<=V; i++){
        if(minn > arr[i][i]){
            minn = arr[i][i];
        }
    }
                        
    if(minn >= INF) printf("-1");
    else printf("%d", minn);
 
    return 0;
}