[Python] 백준 1753번 : 최단경로

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

1753번: 최단경로

---

💡 문제 풀이

그래프 이론 중 다익스트라 알고리즘 문제이다.

 

다익스트라 알고리즘을 알면 바로 풀려 딱히 풀이는 없어도 될 것 같다.

✔️ 느낀 점

처음에는 나만의 코드로 작성하려고 했는데 

이상하게 계속 시간 초과가 발생하길래 리스트로 바꾸어주고 언패킹도 모두 해주었다.

확실히 리스트가 시간이 좀 빠르긴 한가보다.

💻 코드

import sys, heapq
input = sys.stdin.readline
INF = int(1e9)

V, E = map(int, input().split())
K = int(input())
graph = [[] for _ in range(V + 1)]
for _ in range(E):
    u, v, w = map(int, input().split())
    graph[u].append((w, v))
    
dist = [INF] * (V+1)
q = []

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

    while q:
        current_weight, current_node = heapq.heappop(q)

        if dist[current_node] < current_weight: continue

        for next_weight, next_node in graph[current_node]:
            distance = next_weight + current_weight
            if distance < dist[next_node]:
                dist[next_node] = distance
                heapq.heappush(q, (distance, next_node))

Dijkstra(K)
for i in range(1,V+1):
    print("INF" if dist[i] == INF else dist[i])