문제 링크

https://www.acmicpc.net/problem/1916

문제 설명

• start 에서 end 까지 가는 최단거리 출력

풀이

• 다익스트라 알고리즘을 자꾸 까먹어서 다시 한 번 풀어봤다
• start 거리 0, 큐에 푸시
• 반복
  • 인접 노드 순회
    • 작으면 갱신, 푸시

코드

import heapq, sys


def init():
    ipt = sys.stdin.readline
    n = int(ipt())
    m = int(ipt())
    adj_list = [[] for _ in range(n + 1)]
    for _ in range(m):
        s, e, c = map(int, ipt().split())
        adj_list[s].append((e, c))
    start, end = map(int, ipt().split())
    return n, start, end, adj_list


def dijkstra():
    dist = [float('inf')] * (n+1)
    dist[start] = 0
    q = [(0, start)]
    while q:
        cd, cn = heapq.heappop(q)
        for nn, cost in adj_list[cn]:
            nd = cd + cost
            if dist[nn] > nd:
                dist[nn] = nd
                heapq.heappush(q, (nd, nn))
    return dist[end]


n, start, end, adj_list = init()
print(dijkstra())