[백준] 1753 최단경로

문제

• 방향그래프가 주어지면 시작점에서 다른 모든 정점으로의 최단 경로 구하기
• 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.
• 1 <= 정점 개수 V <= 20,000
  1 <= 간선 개수 E <= 300,000

 

풀이

• 다익스트라로 풀 수 있는 전형적인 최단경로 문제
• A -> B 로 가는 간선이 여러 개일 수 있으므로 정렬 후 시작하도록 한다. **
• 시간 초과에 유의하기 위해 입력시 sys.stdin.readline 사용한다.

 

import heapq
import sys
input = sys.stdin.readline

V, E = map(int, input().split())
K = int(input())    # 시작점
# 그래프 입력
graph = [[] for _ in range(V+1)]
for _ in range(E) :
    u, v, w = map(int, input().split())
    graph[u].append((v, w))
# 그래프 정렬
for i in range(V+1) :
    graph[i].sort()

# 다익스트라
INF = int(1e9)
distance = [INF] * (V+1)
distance[K] = 0
q = [(0, K)]

while q :
    dist, now = heapq.heappop(q)

    if distance[now] < dist :
        continue

    for i in graph[now] :
        cost = dist + i[1]
        if cost < distance[i[0]] :
            distance[i[0]] = cost
            heapq.heappush(q, (cost, i[0]))

# 출력
for dist in distance[1:] :
    print(dist if dist != INF else "INF")

 

References

• 백준 최단경로