악곱 == 악성곱슬

다익스트라, 해시, 우선순위 큐

---

해당 문제는 최단 경로를 구하는 문제이다. 문제에서 대놓고 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구해야 하고, 음수 간선이 없기 때문에 다익스트라 알고리즘을 사용할 수 있다.

주어진 입력의 개수가 10000개가 넘어가므로, O(V^2)의 알고리즘을 사용한다면 시간 초과가 발생한다. 따라서 가장 비용이 작은 노드를 선택하는 과정에서 우선순위 큐 자료구조를 사용하여 시간 복잡도를 개선한다.

그리고 문제에서 함정이 있는데, 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수 있기 때문에, 해시(dict)자료구조를 사용하여 인접 리스트를 초기화 한다.

코드는 다음과 같다.

import sys
import heapq

INF = int(1e9)

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        # items 쓸껄..
        for adj in adj_lst[now].keys():
            cost = dist + adj_lst[now][adj]
            if cost < distance[adj]:
                distance[adj] = cost
                heapq.heappush(q, (cost, adj))

def solution(vtx, k):
    dijkstra(k)
    for i in range(1, vtx + 1):
        if distance[i] == INF:
            print("INF")
        else:
            print(distance[i])

if __name__ == "__main__":
    V, E = map(int, sys.stdin.readline().rstrip().split())
    K = int(sys.stdin.readline().rstrip())
    adj_lst = [{} for _ in range(V + 1)]
    distance = [INF] * (V + 1)
    for _ in range(E):
        u, v, Cost = map(int, sys.stdin.readline().rstrip().split())
        try:
            adj_lst[u][v] = min(adj_lst[u][v], Cost)
        except:
            adj_lst[u][v] = Cost
    solution(V, K)