[ SW Expert Academy ] 5251. 최소 이동 거리

 

1차시도 [ 10 / 10 ] PASS

 

다익스트라 알고리즘 적용시켜서 그냥 고대~로 구현했다.

이해보다는 암기의 영역인 문제였다. 응용이 그다지 필요하지 않아서

 

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
        for i in graph[now]:
            cost = dist+i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))


T = int(input())
for test_case in range(1, T+1):
    N, E = map(int, input().split()) # 마지막 연결지점, 도로개수
    distance = [INF]*(N+1)
    graph = [[] for _ in range(E+1)]
    for i in range(E):
        s, e, w = map(int, input().split())
        graph[s].append((e, w))

    dijkstra(0)
    print("#{} {}".format(test_case, distance[N]))