백준 1956 운동

gmlwlswldbs·2022년 1월 21일
0

코딩테스트

목록 보기
124/130
import sys
input = sys.stdin.readline

INF = int(1e9)

v, e = map(int, input().split())
g = [[INF] * v for _ in range(v)]
for _ in range(e):
    a, b, c = map(int, input().split())
    g[a-1][b-1] = c

for k in range(v):
    for i in range(v):
        for j in range(v):
            g[i][j] = min(g[i][j], g[i][k] + g[k][j])
ans = INF
for i in range(v):
    ans = min(ans, g[i][i])
if ans == INF:
    print(-1)
else:
    print(ans)

처음 짠 코드(통과) : 처음에 자기자신에게 가는 경로를 없다고 가정하고 0으로 초기화하지 않고 무한대로 두고 플로이드 와샬함

import sys
input = sys.stdin.readline

INF = int(1e9)

v, e = map(int, input().split())
g = [[INF] * v for _ in range(v)]
for _ in range(e):
    a, b, c = map(int, input().split())
    g[a-1][b-1] = c
for i in range(v):
    g[i][i] = 0

for k in range(v):
    for i in range(v):
        for j in range(v):
            g[i][j] = min(g[i][j], g[i][k] + g[k][j])

ans = INF
for i in range(v):
    for j in range(v):
        ans = min(ans, g[j][i] + g[i][j])

if ans == INF:
    print(-1)
else:
    print(ans)

아예 자기 자신으로 가는 경로를 무한대로 두고 플로이드 와샬하고 나중에 자기 자신 -> 임의의 노드 -> 자기 자신으로 가는 경로 (사이클) 중 최단거리 찾음
=> 왜 안됨??

for i in range(v):
    for j in range(v):
        if i != j:
            ans = min(ans, g[j][i] + g[i][j])

이렇게 자기 자신으로 가는 경로 빼주니까 된다. 자기 자신은 위에서 0이라고 하고 ... 카운트 함...

0개의 댓글