최소비용 구하기 ( 1916 )

1916번: 최소비용 구하기

 

나의 풀이

import heapq
import sys

def _main(city, bus, conn_dict):
    start, end = map(int, sys.stdin.readline().rstrip().split())
    visit = [float("inf")] * city
    queue = []
    heapq.heappush(queue, (0, start))

    while queue:
        now_cost, now_node = heapq.heappop(queue)
        if visit[now_node - 1] < now_cost:
            continue

        for next_node, use_cost in conn_dict[now_node]:
            total_cost = now_cost + use_cost
            if (visit[next_node - 1] > total_cost):
                visit[next_node - 1] = total_cost
                heapq.heappush(queue, (total_cost, next_node))
    return visit[end - 1]

city = int(sys.stdin.readline())
bus = int(sys.stdin.readline())
conn_dict = {i: [] for i in range(1, city + 1)}
for _ in range(bus):
    a, b, cost = map(int, sys.stdin.readline().rstrip().split())
    conn_dict[a].append((b, cost))
print(_main(city, bus, conn_dict))

 

시간 복잡도

while queue : 노드를 탐색 최소 비용을 구하기위해 왔던 루트 다시 탈수도 있음.. ( 이차형 시간 복잡도 )
	now_cost, now_node = heapq.heappop(queue) : heapq 연산 ( 로그 시간 복잡도 )
해당 알고리즘 시간 복잡도 : 이차형 로그 시간 복잡도 ( O(n ** 2 log n )) )