[백준] 1753번 최단경로 (파이썬)

난이도 : GOLD IV

문제링크 : https://www.acmicpc.net/problem/1753

문제해결 아이디어

• 전형적인 다익스트라 최단경로문제이다
• 다익스트라 알고리즘의 핵심은 우선순위큐를 활용하여 비용이 낮은순서로 먼저 처리하고 만약 더낮은 비용으로 처리된 노드가 있다면 continue로 넘어 가는것이라고 생각했다.

소스코드

import sys
import heapq

input = sys.stdin.readline

v,e = map(int, input().split())

start = int(input())

graph = [[] for _ in range(v+1)]
distance = [int(1e9)] * (v+1)

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

def dijk(start):
    distance[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while q:
        dist, now = heapq.heappop(q)

        if distance[now] < dist:
            continue

        for node,cost in graph[now]:
            new_cost = cost + dist
            if new_cost < distance[node]:
                distance[node] = new_cost
                heapq.heappush(q, (new_cost, node))

dijk(start)

for i in range(1, v+1):
    if distance[i] == int(1e9):
        print('INF')
    else:
        print(distance[i])