BOJ 1956번: 운동

호프 2021. 5. 25. 03:30

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

1956번: 운동

첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의

www.acmicpc.net

문제풀이:

플로이드 와샬 알고리즘을 사용하여 문제를 풀었고, pypy로 통과했다.

플로이드 와샬 알고리즘을 사용해야겠다고 생각하는 게 어려운 것 같다.

import sys

V, E = map(int, sys.stdin.readline().split())
INF = 10**10
graph = [[INF]*(V+1) for _ in range(V+1)]
for _ in range(E):
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a][b] = c

for k in range(1,V+1):
    for i in range(1,V+1):
        for j in range(1,V+1):
            graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])

ans = INF
for i in range(1,V+1):
    ans = min(ans, graph[i][i])

if (ans==INF):
    print(-1)
else: print(ans)

저작자표시 (새창열림)