플로이드 ( 11404번 )

11404번: 플로이드

 

나의 풀이

import sys, heapq

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

def _dj(n, conn_dict, start):
    visit = [int(1e9)] * n
    visit[start - 1] = 0
    hq = [(0, start)]

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

    for idx in range(n):
        if (visit[idx] == int(1e9)):
            visit[idx]=0
    return ' '.join(list(map(str, visit)))

n = int(sys.stdin.readline().rstrip())
m = int(sys.stdin.readline().rstrip())
conn_dict = _make_conn_dict(n, m)
for num in range(1, n+1):
    print(_dj(n, conn_dict, num))

 

시간 복잡도

for num in range(1, n+1) : n번 순회 ( 선형 시간 복잡도 )
    print(_dj(n, conn_dict, num)) : 다익스트라 알고리즘 ( 선형 로그 시간 복잡도 )
해당 알고리즘 시간 복잡도 : 이차형 로그 시간 복잡도 ( O(n**2 log n) )