문제

N개의 땅 중에서 한 곳에 자취를 하려고 집을 알아보고 있다. 세 명의 친구
A, B, C가 있는데 이 친구들의 살고 있는 집으로부터 가장 먼 곳에 집을 구하려고 한다.

이때, 가장 먼 곳은 선택할 집에서 거리가 가장 가까운 친구의 집까지의 거리를 기준으로 거리가 가장 먼 곳을 의미한다.

예를 들어, X 위치에 있는 집에서 친구 A, B, C의 집까지의 거리가 각각 3, 5, 4이라 가정하고
Y 위치에 있는 집에서 친구 A, B, C의 집까지의 거리가 각각 5, 7, 2라고 하자.

이때, 친구들의 집으로부터 땅 X와 땅 Y 중 더 먼 곳은 X 위치에 있는 집이 된다. 왜냐하면 X에서 가장 가까운 친구의 집까지의 거리는 3이고, Y에서는 2이기 때문이다.

친구들이 살고 있는 집으로부터 가장 먼 곳을 구해보자.

# 22865
import sys
input = lambda : sys.stdin.readline().strip()
INF = int(1e9)

import heapq
n = int(input())
A, B, C = map(int, input().split())
m = int(input())

graph = [[] for _ in range(n+1)]
distance = [INF] * (n+1)

for _ in range(m):
    a, b, l = map(int, input().split())
    graph[a].append((b, l))
    graph[b].append((a, l))
    
def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
                
dijkstra(A)
dist_A = [i for i in distance]
distance = [INF] * (n+1)

dijkstra(B)
dist_B = [i for i in distance]
distance = [INF] * (n+1)

dijkstra(C)
dist_C = [i for i in distance]

my_home = 0
my_home_i = 0
for i in range(1, n+1):
    dist_now = min(dist_A[i], dist_B[i], dist_C[i])
    if my_home < dist_now:
        my_home = dist_now
        my_home_i = i
        
print(my_home_i)

시간 제한이 1.5초이고, N과 M의 크기가 100,000이 넘으므로 NlogM의 시간복잡도로 풀어야 한다.

백준 22865 가장 먼 곳