[백준] 22865 가장 먼 곳 Python

https://www.acmicpc.net/problem/22865

22865번: 가장 먼 곳

다익스트라 알고리즘을 이용해서 a, b, c로부터 모든 지점까지의 거리를 구한다. 

그 거리들을 담아 놓은 리스트가 dist_a, dist_b, dist_c이다. 

for i in range(1, n+1):
    if max_dist < min(dist_a[i], dist_b[i], dist_c[i]):
        max_dist = min(dist_a[i], dist_b[i], dist_c[i])
        result_area = i 

각 지역 (1 ~ N) 에서 각각 a, b, c 사이의 거리들 중 최솟값을 구하고, 이 최솟값들 중에서 최댓값을 구한다. 

import heapq

n = int(input())
INF = int(1e9)

a, b, c = map(int, input().split())
graph = [[] * (n+1) for _ in range(n+1)]
m = int(input())
for _ in range(m):
    d, e, length = map(int, input().split())
    graph[d].append((e, length)) # 양 방향 그래프 
    graph[e].append((d, length))


def dijkstra(start):
    global graph
    distance = [INF] * (n+1)
    distance[start] = 0 # 자기자신 
    queue = []

    heapq.heappush(queue, (0, start))
    while queue:
        dist, now = heapq.heappop(queue)
        if distance[now] < dist: # 이미 갱신된 거리 값이라면 continue 
            continue 
        for next, next_dist in graph[now]:
            total_dist = dist + next_dist
            if total_dist < distance[next]:
                distance[next] = total_dist
                heapq.heappush(queue, (total_dist, next))
    return distance 

dist_a = dijkstra(a)
dist_b = dijkstra(b)
dist_c = dijkstra(c)
max_dist = 0 
result_area = 0 
for i in range(1, n+1):
    if max_dist < min(dist_a[i], dist_b[i], dist_c[i]):
        max_dist = min(dist_a[i], dist_b[i], dist_c[i])
        result_area = i 

print(result_area)