백준 1753 최단경로 python

• 최단 경로

👨‍💻문제 관찰
간선과 가중치를 가지는 그래프 문제 -> 다익스트라

🔑문제 해설
정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000)
임으로 nlogn 시간 복잡도를 가지는 다익스트라를 구현해야함. 이를 위해선 우선순위큐를 이용해야한다.
기본형 코드니 암기가 필수적이다.

import heapq
INF = int(1e9)

def dijkstra(x):
    q = []
    heapq.heappush(q, (0, x))
    dist[x] = 0
    while q:
        dist_x, x = heapq.heappop(q)
        if dist_x != dist[x]:
            continue
        for u, weight in graph[x]:
            if dist[u] > dist[x] + weight:
                dist[u] = dist[x] + weight
                heapq.heappush(q, (dist[u], u))



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

dijkstra(start)

for i in dist[1:]:
    print(i if i != INF else 'INF')