백준 온라인 저지, 최단경로 / 22865번: 가장먼곳 (파이썬 / 백준 골드문제)

문제 주소: https://www.acmicpc.net/problem/22865

문제

$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$이기 때문이다.

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

입력

첫번째 줄에 자취할 땅 후보의 개수 $N$이 주어진다.

2번째 줄에는 친구 $A$, $B$, $C$가 사는 위치가 공백으로 구분되어 주어진다. 이때 친구들은 $N$개의 땅 중 하나에 사는 것을 보장한다. (같은 위치에서 살 수 있다.)

3번째 줄에는 땅과 땅 사이를 잇는 도로의 개수 $M$이 주어진다.

그 다음줄부터 $M + 3$번째 줄까지 땅 $D$, 땅 $E$, 땅 $D$와 땅 $E$와 사이를 연결하는 도로의 길이 $L$이 공백으로 구분되어 주어진다. 이 도로는 양뱡항 통행이 가능하다.

출력

친구들이 살고 있는 집으로부터 가장 먼 곳의 땅 번호를 출력한다. 만약 가장 먼 곳이 여러 곳이라면 번호가 가장 작은 땅의 번호를 출력한다.

제한

• $ 1 ≤ N ≤ 100,000$
• $N - 1 ≤ M ≤ 500,000$
• $1 ≤ A, B, C, D, E ≤ N$
• $1 ≤ L ≤ 10,000$

예제 입력 1

6
1 2 5
8
1 2 1
2 3 4
1 4 2
2 5 3
1 6 5
5 6 2
3 4 2
4 5 6

예제 출력 1

3

힌트

접근 방법

- a, b, c에서 다익스트라를 사용해 가장 먼 곳을 구한 뒤, 가장 먼 곳의 땅 번호를 출력한다.

코드

# https://www.acmicpc.net/problem/22865
# 접근 방법
# a, b, c에서 다익스트라를 사용해 가장 먼 곳을 구한 뒤, 가장 먼 곳의 땅 번호를 출력한다.
def dijkstra(start):
    distance[start] = 0
    h = []
    heapq.heappush(h, [0, start])
    while h:
        dist, now = heapq.heappop(h)
        if dist > distance[now]:
            continue
        for x in graph[now]:
            cost = dist + x[1] 
            if cost < distance[x[0]]:
                distance[x[0]] = cost
                heapq.heappush(h, [cost, x[0]])

import sys, heapq
input = sys.stdin.readline
n = int(input())
a, b, c = map(int ,input().split())
m = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    d, e, l = map(int ,input().split())
    graph[d].append([e, l])
    graph[e].append([d, l])

INF = 1e10
totalDist = [INF for _ in range(n+1)] # total, min
for i, x in enumerate([a, b, c]):
    distance = [INF for _ in range(n+1)]
    dijkstra(x)
    for j in range(1, n+1):
        totalDist[j] = min(totalDist[j], distance[j])
result = 1
for i in range(2, n+1):
    if totalDist[result] < totalDist[i]:
        result = i
print(result)