[백준/Python] 1753번 최단경로

문제

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

 

소스코드

import sys
import heapq
input = sys.stdin.readline

V, E = map(int, input().split())
k = int(input())
grape = {}
for i in range(E):
    u, v, w = map(int, input().split())
    if u not in grape:
        grape[u] = []
    grape[u].append((v, w))

def dijkstra(start):
    q = []
    distance_list =[1e9 for i in range(V + 1)]
    heapq.heappush(q, (0, start))
    distance_list[start] = 0

    while q:
        current_distance, current_node = heapq.heappop(q)
        if current_distance > distance_list[current_node]:
            continue

        if current_node in grape:
            for neighbor, weight in grape[current_node]:
                distance = current_distance + weight

                if distance < distance_list[neighbor]:
                    distance_list[neighbor] = distance
                    heapq.heappush(q, (distance, neighbor))
    return distance_list
datalist = dijkstra(k)
for i in range(V):
    temp = datalist[i + 1]
    if temp == 1e9:
        print("INF")
    else:
        print(temp)

 

다익스트라 풀이입니다. 

음수 가중치가 없는 그래프에서 사용할 수 있는 최단경로 알고리즘입니다. 

시간복잡도는 우선순위큐를 사용하였다면 O(ElogV)입니다.