JOI 2015 3번 - JOI 公園 (JOI Park) 풀이

[JOI 2015 3번 - JOI 公園 (JOI Park)]

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

10715번: JOI 공원

 
$X$를 결정하는 데 있어, 광장 $1$로부터 광장 $i(2 \leq i \leq N)$까지의 최소 거리가 중요하므로 이 최소 거리들을 먼저 구해봅시다. 문제의 제한이 $2 \leq N \leq 100 000$, $1 \leq M \leq 200 000$이기도 하고, 특정 정점에서 다른 모든 정점까지의 최소 거리를 모두 구하는 데에는 다익스트라 알고리즘이 적합하므로 이를 이용합시다. 
 
최소 거리를 모두 구한 다음엔 어떻게 진행해야 할까요? 정수 $X$를 어떤 값 $k_1$으로 결정하였다고 했을 때, 광장 $i$의 도로 일부분이 철거되었다고 합시다. 이 상태에서 $X$를 $k_2(k_1 \leq k_2)$로 바꾸었다고 해서, 광장 $i$의 철거된 일부분의 도로가 복구될 수는 없습니다. 광장 $i$는 광장 $1$과의 거리가 $k_1$ 이하인데, $k_2$는 $k_1$ 이상이고, 이는 광장 $i$가 여전히 지하도로 연결되어야 할 대상임을 나타내기 때문입니다.
 
따라서 앞서 구했던 최소 거리들을 오름차순으로 정렬하여 $X$의 값을 결정해나간다면, $X$가 변화할 때마다 매번 모든 도로의 철거 여부를 결정하지 않아도 됩니다. 이번 차례에서 어떤 광장 $i$가 지하도 연결 대상이라면(즉, $X$의 값이 광장 $i$의 최소거리와 동일한 상태라면), 광장 $i$에 연결된 도로 중 상대 광장이 이미 지하도 연결 대상일 경우(즉, 상대 광장의 최소거리는 현재 $X$보다 낮거나 같아 이미 이전 차례에서 탐색되었습니다.), 그 도로는 철거되어야 할 도로임을 알 수 있습니다. 따라서 먼저 모든 도로의 길이 $d$의 합을 구한 다음, 철거되어야 할 도로가 발견될 때마다 그 도로의 길이를 빼주면 보수해야 할 도로의 비용을 쉽게 알 수 있습니다.
 
이 과정은 광장과 도로를 한 번씩만 탐색하므로 시간복잡도가 $O(max(N, M))$입니다.
다익스트라 과정의 시간복잡도가 $O(MlgN)$, 최소 거리 정렬의 시간복잡도가 $O(NlgN)$이므로 모든 과정이 시간 안에 돌아감을 알 수 있습니다.