[알고리즘] 백준 1753 최단경로

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

1753번: 최단경로

 

풀이과정.

최단경로를 구하는 문제로 Queue에 간선을 넣어 순서대로 꺼내며 dp배열에 최단 경로를 갱신해나가면 된다고 생각했다.

허나 무수한 '시간초과' 로 상당히 애먹었던 문제.

그 이유는 '서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.'

'유의'란 언급이 있다면 진짜 유의해야한다.

처음에 heapq를 사용하지도 않았다.  우선순위큐를 사용하여 가중치의 최소값우선으로 비교하면 시간이 절약가능했다.

 

>> 유의에 유의 할 것.

>>자료구조 Queue, DP, 우선순위큐

    -> heapq 사용법 복습하기

import sys
import heapq
V,E=map(int,input().split())
K=int(input())
arr=[[] for _ in range(V+1)]
for _ in range(E):
	a,b,c=map(int,sys.stdin.readline().split())
	arr[a].append([b,c])
q=[]
dp=['INF']*(V+1)
dp[K]=0
heapq.heappush(q,[0,K])
while q:
	a,b=heapq.heappop(q)
	if dp[b]!='INF' and dp[b]<a:
		continue
	for t1,t2 in arr[b]:
		if dp[t1]=='INF' or dp[b]+t2<dp[t1]:
			dp[t1]=dp[b]+t2
			heapq.heappush(q,[dp[b]+t2,t1])
for _ in range(1,V+1):
	print(dp[_])