[백준/python/17835] 면접보는 승범이네

문제링크 : 면접보는 승범이네

import sys
import heapq
from collections import defaultdict

input=sys.stdin.readline
inf=sys.maxsize
n,m,k=map(int, input().split())
distance=defaultdict(list)

for _ in range(m):
    u,v,c=map(int, input().split())
    distance[v].append((u,c))
k=list(map(int, input().split()))

def dij():
    q=[]
    d=[float('inf')]*(n+1)
    for i in k:  #모든 면접장 넣어주기
        heapq.heappush(q,(0,i))
        d[i]=1
    while q:
        start_d,start_n=heapq.heappop(q)
        if d[start_n]<start_d:
            continue
        for final_n,final_d in distance[start_n]:
            D=start_d+final_d
            if d[final_n]>D:
                d[final_n]=D
                heapq.heappush(q,(D,final_n))
    return d

d=dij()
index,dist=0,0
for i in range(1,n+1):
    if dist<d[i]:  #면접장과 가장 먼 지원자 찾기
        index,dist=i,d[i]
print(index)
print(dist)

모든 면접장을 heap에 넣어주고 가장 가까운 거리를 찾는다.
모든 지원자의 최소거리 중에 가장 먼 지원자를 찾아서 출력한다.