최소비용 구하기 2 ( 11779번 )

11779번: 최소비용 구하기 2

 

나의 풀이

import sys, heapq

def _make_route(n, bus):
    answer = {i: [] for i in range(1, n + 1)}
    for _ in range(bus):
        s, e, c = map(int, sys.stdin.readline().rstrip().split())
        answer[s].append((e, c))
    return answer

def _Dj(n, routing, source, destination):
    visit = [int(1e9)] * n
    visit[source - 1] = 0
    hq = [(0, source, [source])]

    while hq:
        cost, now_point, now_routing = heapq.heappop(hq)
        if now_point == destination:
            return '\n'.join(map(str, [cost, len(now_routing), ' '.join(map(str, now_routing))]))
        
        for next_point, use_cost in routing[now_point]:
            if (cost + use_cost) < visit[next_point - 1]:
                next_cost = cost + use_cost
                visit[next_point - 1] = next_cost
                heapq.heappush(hq, (next_cost, next_point, now_routing + [next_point]))

n = int(sys.stdin.readline().rstrip())
bus = int(sys.stdin.readline().rstrip())
routing = _make_route(n, bus)
source, destination = map(int, sys.stdin.readline().rstrip().split())
print(_Dj(n, routing, source, destination))

 

시간 복잡도

def _Dj(n, routing, source, destination) : 다익스트라 최단거리
    while hq : 간선을 순회 ( 선형 시간 복잡도 )
		# heappop, push ( 로그 시간 복잡도 )
        heapq.heappop(hq)
        heapq.heappush(hq, (next_cost, next_point, now_routing + [next_point]))

해당 알고리즘 시간 복잡도 : 선형 로그 시간 복잡도 ( O(n log n) )