[백준][다익스트라] 1753. 최단 경로

1753. 최단 경로

 

• 내 풀이
  • 양수의 가중치를 가지는 방향 그래프 -> 다익스트라

from collections import deque, defaultdict
import heapq

v, e = map(int, input().split())
point = int(input())
graph = defaultdict(list)

for _ in range(e):
    start, end, val = map(int, input().split())
    graph[start].append((end, val))

dist = [float('inf') for _ in range(v+1)]

def dijkstra(start):
    queue = []
    heapq.heappush(queue, (0, start))
    dist[start] = 0

    while queue:
        cur_dist, cur = heapq.heappop(queue)

        for nxt, val in graph[cur]:
            if dist[nxt] <= dist[cur]+val:
                continue
            dist[nxt] = dist[cur]+val
            heapq.heappush(queue, (dist[nxt], nxt))


dijkstra(point)
for d in dist[1:]: #첫번째는 0이므로 제외
    if d == float('inf'):
        print("INF")
    else:
        print(d)

 

• 가장 기본 구조

import heapq

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

graph = [[] for _ in range(v+1)]  # 1번~v번 노드 사용

for _ in range(e):
    start, end, val = map(int, input().split())
    graph[start].append((end, val))

dist = [float('inf')] * (v+1)
dist[point] = 0

queue = []
heapq.heappush(queue, (0, point))

while queue:
    cur_dist, cur = heapq.heappop(queue)
    
    # 이미 더 짧은 거리로 처리한 경우 무시
    if cur_dist > dist[cur]:
        continue

    for nxt, val in graph[cur]:
        if dist[nxt] > dist[cur] + val:
            dist[nxt] = dist[cur] + val
            heapq.heappush(queue, (dist[nxt], nxt))

for d in dist[1:]:
    print("INF" if d == float('inf') else d)