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

17835번: 면접보는 승범이네

해당 문제는 데이크스트라로 문제를 해결 할 수 있습니다.

“면접장 까지의 거리”란 그 도시에서 도달 가능한 가장 가까운 면접장 까지의 최단 거리를 뜻한다. 가장 멀리에서 오는 면접자의 거리를 구해야한다.

모든 도시에서 면접장까지 모두 데이크스트라를 이용하여 i번째 도시에서 j번째의 면접장 까지 최단 거리를 구한뒤 거기서 최대 거리를 구해야 할까요?!

<aside> 💡 반대로 생각하여 면접장에서 도시까지 방문해 보는것을 생각해보자.

</aside>

각각의 면접장에서 동시에 출발하여 각각의 도시까지의 최단거리를 구하면 문제를 해결 할 수 있다. BFS의 특성을 잘이해 해야 한다.

import sys
import heapq
from pprint import pprint
input = sys.stdin.readline

N, M, K = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    U, V, C = map(int, input().split())
    graph[V].append((C, U)) # 거꾸로 탐색하기위해 거꾸로 넣는다.

ic = list(map(int, input().split()))

maxidx = 0
maxdistance = 0
visited = [100000*500000 for _ in range(N+1)]
queue = []

for init in graph:
    init.sort()

for k in ic:
    heapq.heappush(queue, (0, k))
    visited[k] = 0

maxvalue = 0
maxidx = 0
while queue:
    cost, target = heapq.heappop(queue)

    if cost > visited[target]:
        continue

    if cost >= maxvalue:
        if maxvalue == cost and target > maxidx:
            pass
        else:
            maxidx = target

        maxvalue = cost

    for dis, newidx in graph[target]:
        if visited[newidx] > cost + dis:
            visited[newidx] = cost + dis
            heapq.heappush(queue, (dis + cost, newidx))

#pprint(visited)
print(maxidx)
print(maxvalue)