(c++) 플로이드-워셜 알고리즘 1956번: 운동

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

1956번: 운동

 

---

 

문제 해결

 

 

모든 정점들에서 자기 자신으로 돌아오는 최단 거리이기에

플로이드-워셜 알고리즘을 사용해야 한다는 것을 알아챘을 것이다.

 

원래 플로이드-워셜 알고리즘은 자기 자신의 거리를 0으로 초기화시키고 시작하는데

자기 자신으로 돌아오는 거리를 알려면 모두 INF로 초기화해주게 된다면

 

자기 자신으로 돌아가는 거리 또한 계산에 포함되게 된다.

그렇다면 그중에서 최소를 구하는 것은

 

graph[i][i]의 최소값을 출력해주고, 모두 INF 값이면 -1을 출력해주면 된다.

 

 

코드

 

 

#include <bits/stdc++.h>
#define INF 4000001
using namespace std;

int V, E;

int graph[401][401];

void cycle() {
    for (int k = 0; k < V; k++) {
        for (int i = 1; i <= V; i++) {
            for (int j = 1; j <= V; j++) {
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
            }
        }
    }
}
int main(void) {
    cin >> V >> E;
    for (int i = 0; i < 401; i++) {
        fill(graph[i], graph[i]+401, INF);
    }
    for (int i = 0; i < E; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a][b] = c;
    }
    cycle();
    int result = INF;
    // 출력
    for (int i = 1; i <= V; i++) {
        if (graph[i][i] != INF) {
            result = min(result, graph[i][i]);
        }
    }
    if (result != INF) {
        cout << result;
    } else cout << -1;
}