백준 17835번: 면접보는 승범이네

백준 17835번: 면접보는 승범이네

풀이 과정

처음에는 다익스트라를 K번 돌리려다가 최악의 경우 N번 돌려야 해서 포기했다. 그래서 생각한 방법은 우선 간선을 입력받을 때 역방향으로 저장해두고 다익스트라 큐에 면접장을 한 번에 다 넣은 다음, 각 도시로 뻗어나가는 것이다. 결과는 성공!

정답 코드

import sys
from heapq import heappush, heappop
from collections import defaultdict
input = sys.stdin.readline


def dijkstra():
    Q = list()
    D = [float('inf')] * (N + 1)
    
    for i in K:
        heappush(Q, (0, i))
        D[i] = 1
    
    while Q:
        SD, SN = heappop(Q)

        if D[SN] < SD:
            continue
            
        for FN, FD in L[SN]:
            d = SD + FD
            if D[FN] > d:
                D[FN] = d
                heappush(Q, (d, FN))

    return D


N, M, K = map(int, input().split())
L = defaultdict(list)
for i in range(M):
    U, V, C = map(int, input().split())
    L[V].append((U, C))
K = list(map(int, input().split()))

D = dijkstra()
index, dist = 0, 0
for i in range(1, N + 1):
    if dist < D[i]:
        index, dist = i, D[i]
print(index)
print(dist)

새롭게 배운 점

우선 순위 큐에 한 번에 다 넣어도 된다..!