[백준 22865번] 파이썬 - 가장 먼 곳

import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline
from heapq import heappop, heappush

def dijkstra(q):
while q:
val, node = heappop(q)
if dist[node] < val:
continue
for next_node, next_val in graph[node]:
temp = val+next_val
if dist[next_node] > temp:
dist[next_node] = temp
heappush(q, [temp, next_node])

N = int(input())
lives = list(map(int, input().split()))
lives = set(lives)
M = int(input())
graph = [[] for _ in range(N+1)]
for _ in range(M):
a, b, c = map(int, input().split())
graph[a].append((b, c))
graph[b].append((a, c))
dist = [float('inf')] * (N+1)
dist[0] = 0
q = []
for i in lives:
dist[i] = 0
heappush(q, [0, i])
dijkstra(q)

result, temp = 0, 0
for idx, v in enumerate(dist):
if v > result:
result = v
temp = idx
print(temp)