[파이썬] 백준 1753 : 최단경로 (골드4)

[파이썬] 백준 1753 : 최단경로 (골드4)

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

---

풀이

방향성 생각

• 방향 그래프의 node A에서 다른 노드까지의 거리를 구하는 문제

• 입력 크기를 보면 node = 20000에 edges = 300000이라 다익스트라로 풀이.

• 주의할점은 node간 중복 간선이 주어져서 처리를 해야한다.

• defaultdict로 이중 딕셔너리 만들어서 최솟값으로 갱신하는 방식으로 풀이

---

전체코드

from collections import defaultdict as dd
import heapq as hq
import sys

input = lambda : sys.stdin.readline().rstrip()

N,K = map(int,input().split())
start = int(input())

# 방향 그래프 : edges[a][b] = cost (a->b로 가는 cost 최소값으로 갱신하기)
edges = dd(lambda : dd(lambda : float('inf')))
for _ in range(K):
    a,b,cost = map(int,input().split())
    edges[a][b] = min(edges[a][b],cost)

V = [float('inf')]*(N+1)
V[start] = 0

heap = [(0,start)]
while heap:

    c,x = hq.heappop(heap)
    for nx,cost in edges[x].items():
        nc = c+cost
        if nc < V[nx]:
            V[nx] = nc
            hq.heappush(heap,(nc,nx))

for cost in V[1:]:
    print(cost if cost != float('inf') else 'INF')

코멘트

• 기본 다익스트라 문제.