[백준/BOJ] 1753 - 최단경로

1753 - 최단경로

📌 문제

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

📋 코드

import heapq

def dijkstra(start, distance):
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0

    while q:
        weight, v = heapq.heappop(q)

        if distance[v] >= weight:
            for i, cost in graph[v]:
                new_cost = weight + cost

                if distance[i] > new_cost:
                    distance[i] = new_cost
                    heapq.heappush(q, (new_cost, i))


INF = int(1e9)

V, E = map(int, input().split())
start = int(input())
graph = [[] for _ in range(V + 1)]

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

distance = [INF] * (V + 1)

dijkstra(start, distance)
[print('INF' if dist == INF else dist) for dist in distance[1:]]

💡 한마디

기본적인 다익스트라 알고리즘으로 풀 수 있다.

1753번: 최단경로