운동

❓문제

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

❗문제 정리

플루이드 알고리즘

📑코드

import sys
input=sys.stdin.readline

v, e=map(int, input().split())
INF=int(1e9)
graph=[[INF]*(v+1) for _ in range(v+1)]

#거리 입력받고 그 값으로초기화
for i in range(e):
    a,b,c=map(int, input().split())
    graph[a][b]=c

    #점화식 사용
for k 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][b],graph[a][k]+graph[k][b])

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

📝코드 설명

1. 필요한 라이브러리 임포트, 인수받기, 최단거리 표현하기 위한 graph만들기

import sys
input=sys.stdin.readline

v, e=map(int, input().split())
INF=int(1e9)
graph=[[INF]*(v+1) for _ in range(v+1)]

#거리 입력받고 그 값으로초기화
for i in range(e):
    a,b,c=map(int, input().split())
	graph[a][b]=c

v(int) : 마을 개수==노드개수
e(int) : 도로 개수==간선개수

최단거리를 표현하기 위한 graph (크기 : 노드수+1 x 노드수+1) 를 INF로 초기화시킨다.
a(int) : 출발지점 , b(int) : 도착지점 , c(int) : a에서 b까지의 거리
도로쌍이 여러번 주어져 있지 않는다는 조건이 있으므로, [출발위치][도착위치]에 거리를 넣어준다.

그래프 예시

2. 플루이드 알고리즘

for k 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][b],graph[a][k]+graph[k][b])

a에서 b까지의 거리=min(a에서 b까지의 거리 , k를 거쳐가는 거리)=min(a에서 b까지의 거리 , a에서 k까지의 거리+k부터 b까지의 거리)

3. 사이클 최단거리 출력하기
   사이클 : 시작지점으로 되돌아오기
   따라서 시작지점과 도착지점이 같은 인덱스값을 보고, 그 인덱스가 INF가 아닌 경우 왕복 최단거리를 출력한다. INF인 경우, -1을 출력한다.

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

최소 사이클의 거리를 출력하라 했으므로, min_cycle를 이용하여 시작위치==도착위치가 같은 값들 중 가장 작은 값을 취함.

🎖제출 결과

💡insight

71%에서 멈춘다면, 최솟값 출력시 else:를 넣어주기
시간초과로 인해 pypy사용.