[백준] 1956번 운동

[적용한 알고리즘]

그래프, 플로이드-와샬

 

[아이디어]

플로이드는 음의 간선이 없는 사이클을 도는 것까지

dist[i][i] (i = 1~N) 까지 나타내므로..

 

[교훈]

플로이드 와샬 알고리즘은 사이클까지 나타내준다..? 정도?

 

<코드>

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int MAX_V = 401;
const int INF = 1000000000;

int V, E;
int Dist[MAX_V][MAX_V];
int main(){
    scanf("%d %d", &V, &E);
    for (int i = 0; i < E; i++){
        int from, to, cost;
        scanf("%d %d %d", &from, &to, &cost);
        Dist[from][to] = cost;
    }

    for (int i = 1; i <= V; i++){
        for (int j = 1; j <= V; j++){
            if (Dist[i][j] != 0) continue;
            Dist[i][j] = INF;
        }
    }

    for (int k = 1; k <= V; k++){
        for (int i = 1; i <= V; i++){
            for (int j = 1; j <= V; j++){
                Dist[i][j] = min(Dist[i][j], Dist[i][k] + Dist[k][j]);
            }
        }
    }

    int ans = INF;
    for (int i = 1; i <= V; i++){
        ans = min(ans, Dist[i][i]);
    }

    printf("%d\n", ans == INF ? -1 : ans);
    return 0;
}