[ 22865 ] [ Dijkstra ] 가장 먼 곳

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

22865번: 가장 먼 곳

---

풀이 과정

---

1. A지점, B지점, C지점에서 시작해서 다익스트라 알고리즘 적용
   • 그러면.. A지점에서 각 지점까지의 거리, B 지점에서 각 지점까지의 거리, C 지점에서 각 지점까지의 거리가 따로 나오게 된다.
2. 각각의 지점에서 A지점, B지점, C지점까지의 거리의 최솟값을 구한다.
   1. A, B, C를 다익스트라 알고리즘으로 구해진 거리, A[i]는 A지점에서 i지점까지의 거리
   2. 예시로 2번 지점이라고 할때, min(A[2], B[2], C[2])를 해주면 된다.
3. (2)의 최댓값이 나올 때의 지점 번호를 구해서 출력해주면 된다. 지점 번호의 경우 최솟값이 같은 경우 번호가 작은걸 출력해주라 하였으므로 지점 번호를을 왼쪽(1)에서 오른쪽(n)으로 진행하면서 갱신한다.

---

소스 코드

---

 

import sys
import heapq

input = lambda : sys.stdin.readline().rstrip()

N = int(input())
A, B, C = map(int, input().split())

graph = [[] for _ in range(N+1)]
M = int(input())

for _ in range(M):
    D, E, L = map(int, input().split())
    graph[D].append([E, L])
    graph[E].append([D, L])

def dijkstra(graph, start):
    INT_MAX = int(10e9)
    distance = [INT_MAX] * len(graph)
    distance[start] = 0
    heap = [[0, start]]
    while heap:
        dist, node = heapq.heappop(heap)
        if distance[node] != dist:
            continue

        for next_node, next_dist in graph[node]:
            if dist + next_dist < distance[next_node]:
                distance[next_node] = dist + next_dist
                heapq.heappush(heap, [distance[next_node], next_node])

    return distance

max_size = 0
answer = 0
dist_a = dijkstra(graph, A)
dist_b = dijkstra(graph, B)
dist_c = dijkstra(graph, C)

for i in range(1, N+1):
    if max_size < min(dist_a[i], dist_b[i], dist_c[i]):
        max_size = min(dist_a[i], dist_b[i], dist_c[i])
        answer = i
        
print(answer)