[다익스트라 알고리즘] 최단경로

기출 : 백준 1753

 

일반적인 다익스트라 문제다

두 정점 사이에 여러 간선이 있을 수 있다는 점을 고려해야 한다

 

from heapq import heappush, heappop
INF = int(1e9)

v, e = map(int, input().split())
k = int(input())
distance = [INF for _ in range(v+1)]
minVal = dict()
graph = [[] for _ in range(v+1)]
queue = list()


for _ in range(e):
    x, y, w = map(int,input().split())
    if x not in minVal:
        minVal[x] = dict()
    if y not in minVal[x]:
        minVal[x][y] = w
        graph[x].append([w,y])
    else:
        if w < minVal[x][y]:
            minVal[x][y] = min(minVal[x][y], w)
            for i in range(len(graph[x])):
                if graph[x][i][1] == y:
                    graph[x][i] = [w,y]
                    break

def djikstra(start):
    distance[start] = 0
    heappush(queue,(0,start))
    while queue:
        curVal, cur = heappop(queue)
        if distance[cur] < curVal:
            continue
        for nextVal, next in graph[cur]:
            if distance[next] > curVal + nextVal:
                distance[next] = curVal + nextVal
                heappush(queue, (curVal + nextVal, next))
        
    return 0

djikstra(k)

for i in range(1,v+1):
    if distance[i]==INF:
        print("INF")
    else:
        print(distance[i])