[Python] BOJ/백준 1956번 운동

[문제]

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

1956번: 운동

 

[풀이]

2022.08.23 - [문제풀이/BOJ] - [Python] BOJ/백준 11404번 플로이드

[Python] BOJ/백준 11404번 플로이드

위 문제랑 엄청 엄청 유사한 문제!!

 

 

[코드]

import sys
INF = int(1e9)

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

for k in range(V):
    for i in range(V):
        for j in range(V):
            if my_map[i][j] > my_map[i][k] + my_map[k][j]:
                my_map[i][j] = my_map[i][k] + my_map[k][j]

answer = INF
for i in range(V):
    for j in range(V):
        answer = min(answer, my_map[i][j] + my_map[j][i])

if answer == INF:
    print('-1')
else:
    print(answer)