1. 문제 설명

면접보는 승범이네

2. 문제 분석

도시에서 면접장까지 걸리는 최단 거리를 다익스트라 알고리즘을 통해 구한 뒤, 최댓값 및 도시 번호를 구한다.

• 도시에서 면접장까지의 거리가 아니라 면접장에서 도시까지 걸리는 거리를 구해야 한 번에 구할 수 있다. 단방향 그래프이므로 그래프 구현시 거꾸로 구현해준다. 다익스트라 알고리즘 역시 출발점(면접장) 모두를 한 번에 우선순위 큐에 넣고 돌린다. 최종적으로 원하는 결과가 면접장에서 가장 가까운 도시까지 걸리는 거리 중 최댓값이기 때문이다.

3. 나의 풀이

import sys
import heapq
from collections import deque

INF = sys.maxsize
n, m, k = map(int, sys.stdin.readline().rstrip().split())
nodes = [[] for _ in range(n+1)]
for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().rstrip().split())
    nodes[b].append([a, c])
interviews = list(map(int, sys.stdin.readline().rstrip().split()))

def Dijkstra():
    distances = [INF for _ in range(n+1)]
    pq = []
    for interview in interviews:
        heapq.heappush(pq, [0, interview])
        distances[interview] = 0

    while pq:
        cur_cost, cur_node = heapq.heappop(pq)

        if distances[cur_node] < cur_cost: continue

        for next_node, next_cost in nodes[cur_node]:
            if distances[next_node] > cur_cost + next_cost:
                distances[next_node] = cur_cost + next_cost
                heapq.heappush(pq, [cur_cost + next_cost, next_node])
    return distances

distances = Dijkstra()
dist = max(distances[1:])
print(distances.index(dist))
print(dist)