[백준] 1956번 운동 - 파이썬

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

1956번: 운동

플로이드워셜 알고리즘을 이용하면 쉽게 풀수 있는 문제이다.

플로이드 워셜 알고리즘은 a -> b로 가는 최단 경로를 찾는 문제이기 때문에 이문제에 적합한 알고리즘이라 생각했다.

다만 약간 다른점은 왕복이므로 최단 경로 그래프에서 a -> b -> a의 값을 구해야한다.

그리고 마지막 조건 만약에 존재하지않을때 -1을 출력하는 조건을 꼭 붙이자 

이거 때문에 시간 너무 날림 

import sys


v, e = map(int,sys.stdin.readline().split())
q = []
INF = int(1e9)
graph= [[INF]*(v+1) for _ in range(v+1)]
for i in range(1,v+1):
    for j in range(1,v+1):
        if i == j:
            graph[i][j] = 0
for _ in range(e):
    a,b,c = map(int,sys.stdin.readline().split())
    graph[a][b] = c

for i in range(1,v+1):
    for a in range(1,v+1):
        for b in range(1,v+1):
            graph[a][b] = min(graph[a][i]+graph[i][b],graph[a][b])
answer = INF
for a in range(1,v+1):
    for b in range(1,v+1):
        if a !=b:
            answer = min(answer, graph[a][b] + graph[b][a])
if answer == INF:
    print(-1)
else:
    print(answer)

 

https://zoozoozoo.tistory.com/400

플로이드 워셜 알고리즘