최단경로 ( 1753번 )

1753번: 최단경로

 

나의 풀이

import heapq
import sys

def _make_conn_dict(v, e):
    conn_dict = {i: [] for i in range(1, v+1)}
    for _ in range(e):
        a, b, c = map(int, sys.stdin.readline().rstrip().split())
        conn_dict[a].append((b, c))
    return conn_dict

def _Dj(start, v, conn_dict):
    visit = [float('inf')] * v
    visit[start - 1] = 0
    hq = [(0, start)]

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

        for next_point, next_cost in conn_dict[now_point]:
            if (visit[next_point - 1] > (now_cost + next_cost)):
                visit[next_point - 1] = (now_cost + next_cost)
                heapq.heappush(hq, ((now_cost + next_cost), next_point))
    return visit  

v, e = map(int, sys.stdin.readline().rstrip().split())
start = int(sys.stdin.readline())
conn_dict = _make_conn_dict(v, e)

for i in _Dj(start, v, conn_dict):
    print('INF') if (i == float('inf')) else print(i)

 

시간 복잡도

_Dj(start, v, conn_dict) : 그래프 탐색 ( O(V + E) )
    heapq.heappop() : 로그 시간 복잡도
    heapq.heappush() : 로그 시간 복잡도
해당 알고리즘 시간 복잡도 : 선형 로그 시간복잡도 ( O(V + E) log n )