[백준] 1753 최단경로 [Python, 파이썬]

• 문제 : https://www.acmicpc.net/problem/1753
• 🔑 기본 다익스트라
  • 출발지에서 모든 노드까지의 거리를 출력
  • 자신의 위치 0 출력
  • 갈 수 없으면 INF 출력
  • 출력 신경쓸 필요 없이 그냥 다익스트라 실행하고 1번 노드부터 순서대로 출력하면 그대로 나옴
  • INF 값만 따로 처리

 

from collections import defaultdict
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

V, E = map(int, input().split())    # 노드의 개수, 간선의 개수
start = int(input())                # 시작 노드

graph = defaultdict(list)

for i in range(E):             
    u, v, w = map(int, input().split()) # 출발, 도착, 가중치
    graph[u].append((w, v))             # 출발 : [(가중치, 도착)...]

INF = int(1e9)
distance = [INF] * (V+1)
distance[start] = 0                     
q = []
heappush(q, (0, start))                

while q:
    now_d, now_n = heappop(q)           # 현재 가중치, 현재 노드

    if now_d > distance[now_n]:         # 현재 위치에 저장된 값보다 현재 가중치가 더 크면 가지마
        continue

    for next_d, next_n in graph[now_n]:
        new_d = now_d + next_d          
        if distance[next_n] > new_d:
            distance[next_n] = new_d
            heappush(q, (new_d, next_n))

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