[백준] 1753번 문제 (최단경로) 파이썬(Python) 풀이

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

1753번: 최단경로

import heapq
import sys
from collections import defaultdict
input = sys.stdin.readline

n, m = map(int, input().split())

graph = defaultdict(list)
distances = [sys.maxsize] * (n + 1)
start = int(input())

for _ in range(m):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))

q = []

heapq.heappush(q, (0, start))

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

    if distances[now] < dist:
        continue

    for node in graph[now]:
        cost = dist + node[1]
        if distances[node[0]] > cost:
            distances[node[0]] = cost
            heapq.heappush(q, (cost, node[0]))

for i in range(1, n + 1):
    if i == start:
        print(0)
    elif distances[i] == sys.maxsize:
        print("INF")
    else:
        print(distances[i])

다익스트라 문제다.

이 문제를 풀기 위해서는 다익스트라 알고리즘의 구현법을 선행해야한다.

 

다익스트라 알고리즘을 알고 있다면 어렵지 않게 풀 수 있을듯하다.