[파이썬] 백준 1956 : 운동 (골드4)

[파이썬] 백준 1956 : 운동 (골드4)

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

---

풀이

방향성 생각

• 사이클이 a -> b -> a로도 생긴다는 것을 알려줌.
• N = 400이라 N^3으로도 가능한 플로이드워셜 사용
• 다익같은 경우, 간선이 N^^2까지 주어져서 시간/메모리 관리를 빡빡하게 해야할듯..

---

전체코드

import sys
input = lambda : sys.stdin.readline().rstrip()
INF = sys.maxsize

N,M = map(int,input().split())

G = [[INF]*(N+1) for _ in range(N+1)]
for _ in range(M):
    a,b,cost = map(int,input().split())
    G[a][b] = cost

# 초기화
for i in range(1,N+1):
    G[i][i] = 0

# 경유지점 k를 거치는 i->j
for k in range(1,N+1): 
    for i in range(1,N+1):
        for j in range(1,N+1):
            G[i][j] = min(G[i][j],G[i][k]+G[k][j])

# 정답출력
answer = INF
for i in range(N+1):
    for j in range(N+1):
        if i!=j:
            answer = min(answer,G[i][j]+G[j][i])
print(answer if answer != INF else -1)

---

코멘트

• 플로이드워셜 기본