BOJ 1753 최단경로

태그

그래프 이론

최단 경로

데이크스트라

생성일

2024/12/11 12:13

URL

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

문제 설명

•

방향 그래프가 주어지면, 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 문제

예제 입력/출력

•

입력1

Plain Text
복사

•

출력1

0
2
3
7
INF
Plain Text
복사

제약 조건

•

1≤V≤20,0001 ≤ V ≤ 20,0001≤V≤20,000

◦

VVV: 정점의 개수

•

1≤E≤300,0001 ≤ E ≤ 300,0001≤E≤300,000

◦

EEE: 간선의 개수

◦

1≤1 ≤1≤ 간선의 가중치 ≤10≤ 10≤10

문제 풀이

•

다익스트라 알고리즘을 이용하여 문제를 해결하면 된다. - O(E⋅logV)O(E \cdot logV)O(E⋅logV)

◦

모든 간선의 가중치가 0 이상이므로 다익스트라 알고리즘 사용 가능

풀이 코드

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

from queue import PriorityQueue

INF = int(1e12)

# input
V, E = map(int, input().split())
K = int(input())

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

# solve (다익스트라)
dist = [INF] * (V + 1)

pq = PriorityQueue()
dist[K] = 0
pq.put([0, K])

while not pq.empty():
	cur_dist, cur_node = pq.get()
	for adj_node, adj_dist in adj_list[cur_node]:
		temp_dist = cur_dist + adj_dist
		if temp_dist < dist[adj_node]:
			dist[adj_node] = temp_dist
			pq.put([temp_dist, adj_node])

for d in dist[1:]:
    print(d if d != INF else 'INF')
Python
복사