[백준1956&파이썬] 플로이드-와샬을 이용해 왕복 최단거리를 찾아보자

# 문제

백준 1956 운동 파이썬 풀이

1956번: 운동

# 코드

'''
  # 플로이드 와샬로 전체 경로 구하고, a->b , b->a의 값으로 사이클여부 판단과 동시에 최단경로 출력이 가능해보이는 문제
'''
import sys

V,E = map(int,sys.stdin.readline().split())
distance = [[float('inf')] * (V+1) for _ in range(V+1)]

for _ in range(E) :
  a,b,c = map(int,sys.stdin.readline().split())
  distance[a][b] = c # 단방향 연결 #같은 도로 여러개 주어지지 않음

for _ in range(V+1) :
  distance[_][_] = 0 # 자기 자신 초기화

for pivot in range(1,V+1) :
  for start in range(1,V+1) :
    for end in range(1,V+1) :
      distance[start][end] = min(distance[start][end], distance[start][pivot] + distance[pivot][end])

mmin = float('inf')
for start in range(1,V+1) :
  for end in range(1,V+1) :
    if start == end :
      continue
    sum = distance[start][end] + distance[end][start]
    mmin = min(sum,mmin)

if mmin == float('inf') :
  print(-1)
else :
  print(mmin)

# 풀이

왕복이 가능해야한다. 이를 판단하기 위해서 플로이드 와샬을 사용한다면 모든 정점에서부터 모든 정점까지의 최단거리를 알 수 있다.

왕복이 불가능하다면 a->b / b->a 둘중의 하나가 INF가 될 것이다. 이 정보를 잘 활용하면 문제를 해결 할 수 있었다.

반복문을 이용해 a->b / b->a의 모든 값들 중 최소값을 뽑자.