알고리즘 문제/알고리즘 노트
다익스트라 알고리즘
태윤2
2020. 10. 27. 19:54
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
# 다익스트라 알고리즘 최단경로
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)
v,e = map(int,input().split())
start = int(input())
graph = [[] for _ in range(v+1)]
distance = [INF] * 20001
for i in range(e):
a,b,c = map(int,input().split())
graph[a].append((b,c))
def dijkstra(start):
q= []
heapq.heappush(q,(0,start))
distance[start] = 0
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]))
dijkstra(start)
for i in range(1,v+1):
if distance[i] == INF :
print('INF')
else:
print(distance[i])
|
cs |