Koala - 13기/코딩테스트 준비 스터디
[백준/Python] 5972번 택배 배송
Langerak
2024. 2. 24. 16:21
문제
풀이
1부터 N까지의 노드가 있고, 1에서 N까지 가는 최단 거리를 찾는 문제와 동일하다.
다익스트라를 사용하여 최단 거리를 구해주었다.
코드
import sys
from heapq import heappop, heappush
input = sys.stdin.readline
INF = 1e9
def dijkstra(graph, n):
hq = [(0, 1)]
distance = [1e9] * (n + 1)
distance[1] = 0
while hq:
dist, cur = heappop(hq)
if dist > distance[cur]:
continue # 예외 처리
for weight, next_node in graph[cur]:
next_dist = dist + weight
if next_dist < distance[next_node]:
distance[next_node] = next_dist
heappush(hq, (next_dist, next_node))
print(distance[n])
def main():
n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
s, e, w = map(int, input().split())
graph[s].append((w, e))
graph[e].append((w, s))
dijkstra(graph, n)
if __name__ == "__main__":
main()