1956_운동

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

1956번: 운동

 

 

이제 그래프를 활용해서 최단거리를 구하는 것은 익숙해졌다! 사이클을 구하기 위해서 어떻게 해야할까 고민하다가

결국 사이클이란 것은 본인에서 시작해서 본인으로 돌아오는 최단거리라고 생각했다.

 

지금까지 코드를 구현할때는 1번에서 1번으로 가는것은 0으로 두었었는데, 이를 그냥 설정하지 않고 코드를 진행시키고, INF가 아닌 최솟값을 찾는 코드를 구현하면 될것같아서 해 보았더니 동작하였다!

 

import sys
import heapq
input = sys.stdin.readline
INF = int(1e9)
v,e = map(int,input().split())
graph = [ [] for _ in range(v+1) ]

for _ in range(e):
    a,b,c = map(int,input().split())
    graph[a].append((b,c))

dist = [ [INF] * (v + 1) for _ in range(v+1) ]

def f(start):
    #dist[start][start] = 0
    q = []
    heapq.heappush(q,(start,0))

    while q:
        node,cnt = heapq.heappop(q)

        if dist[start][node] < cnt:
            continue
        for i,j in graph[node]:
            if dist[start][i] > cnt + j:
                dist[start][i] = cnt + j
                heapq.heappush(q,(i,cnt+j))

for i in range(1,v+1):
    f(i)
result = INF
for i in range(1,v+1):
    result = min(result,dist[i][i])
print(result if result != INF else -1)