문제링크 : 면접보는 승범이네
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에 넣어주고 가장 가까운 거리를 찾는다.
모든 지원자의 최소거리 중에 가장 먼 지원자를 찾아서 출력한다.