백준 14284 간선 이어가기 2 - 골드5 [파이썬]

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

14284번: 간선 이어가기 2

 

문제를 딱 읽어보니 최소 루트를 구하는 다익스트라 문제같았다.

그래서 다익스트라를 사용해서 풀었더니 통과됐다.

 

import sys
import heapq
input = sys.stdin.readline

N, M = map(int, input().split(" "))
graph = [[] for i in range(N+1)]
INF = sys.maxsize
distance = [INF for i in range(N+1)]
for i in range(M):
    a, b, val = map(int, input().split(" "))
    graph[a].append((b, val))
    graph[b].append((a, val))
finalA, finalB = map(int, input().split(" "))
distance[finalA] = 0

heap = []
for i in graph[finalA]:
    to, val = i[0], i[1]
    heapq.heappush(heap, (to, val))
    distance[to] = val

while heap:
    fr, val = heapq.heappop(heap)
    for j in graph[fr]:
        to, toval = j[0], j[1]
        newVal = val + toval
        if distance[to] > newVal:
            distance[to] = newVal
            heapq.heappush(heap, (to, newVal))

print(distance[finalB])

# 다익스트라

while문을 for문 안에 넣었더니 한 번 틀렸다.

굳이 안넣어도 되기때문에 for문 바깥으로 뺐더니 통과됐다.