백준 온라인 저지, 최단경로 / 19584번: 난개발 (파이썬 / 백준 골드문제)

문제

이 사실은 대회에 참가하고 있는 여러분들만 알고 있는 사실이다. 방금 외계인들이 지구를 정복했고 서울시청과 서울시의회를 장악했다. 이들은 인간들이 통근과 통학으로 고통받게 하려고 대규모 토목공사를 기획하고 있는데, 바로 지상에 서울 지하철 10호선을 짓는 것이다.

‘10호선을 만들어 준다니 좋은 거 아닌가?’라고 생각할지도 모르겠지만, 이들의 목적은 따로 있다. 바로 도로들을 철도노선으로 전부 가로막아 버리는 것이다. 이렇게 되면 서울의 남북을 가로지르는 버스 노선은 전부 사라지게 된다.

좋은 소식은 여러분들이 이 계획을 알고 있다는 것이다.

외계인들은 뛰어난 건축 기술을 갖고 있지만 x축에 평행하도록 철길을 놓을 때 가장 빠르게 철길을 완성할 수 있으므로 그렇게 할 것이다. 철길의 시점과 종점은 서울 바깥에 있으며, 철길과 도로가 만나면 도로는 전부 철거된다. 도로의 시점이나 종점이 철길과 만나는 경우에도 도로가 철거된다.

외계인들은 철거될 도로들의 통행량의 합이 가장 큰 곳에 철길을 놓으려 한다.

서울시내 주요 장소 N개의 직교좌표계상의 좌표와, 이를 잇는 도로 총 M개의 정보가 주어지면 외계인들이 어디에 10호선을 지을지 예상하는 프로그램을 작성하자.

입력

첫째 줄에는 N과 M이 주어진다. (2 ≤ N ≤ 2 × 10⁵, 1 ≤ M ≤ 2 × 10⁵)

이후 N줄에 걸쳐 한 줄에 하나씩 서울시내 주요 장소들의 x좌표와 y좌표가 공백으로 구분되어 주어진다. 좌표는 정수이며 그 절댓값은 10⁹를 넘지 않는다.

이후 M줄에 걸쳐 한 줄에 하나씩 세 정수 u_i, v_i, c_i가 주어진다. (1 ≤ u_i, v_i ≤ N, u_i ≠ v_i, 0 ≤ c_i ≤ 10⁹) 이는 u_i번째 장소와 v_i번째 장소를 잇는 통행량 c_i의 도로가 있음을 의미한다. 각 도로는 직선형으로 u_i번째 장소와 v_i번째 장소를 최단 거리로 연결해 준다. 도로는 교차할 수는 있으나, 한 도로로 주행 중 다른 도로로 진입할 수는 없다. 같은 장소를 잇는 도로가 여러 개 존재할 수 있다.

출력

외계인들이 철도노선을 지었을 때 최대로 파괴되는 통행량을 출력한다.

제한

예제 입력 1

5 4
1 3
4 4
2 4
5 0
3 2
1 3 5
3 5 1
5 4 3
2 5 4

예제 출력 1

10

힌트

접근 방법

- 0. 주어진 도시(city)의 위치를 입력받고, 도로(road)에 대한 정보를 입력받는다. 단, 도로에 대한 정보를 입력받을 때는 각 도시의 y좌표를 입력받는다.
- 1. road를 오름차순으로 정렬한 뒤, 하나씩 탐색한다.
- 2. 만약 현재 탐색 중인 도로의 더 낮은 y좌표의 도시보다 최소힙의 0번째 인덱스의 값이 더 작다면 이를 반복적으로 삭제한다.
- 3. 각 도로를 탐색할 때 더 높은 y좌표를 기준으로 최소힙에 삽입한다.
- 4. 이후 힙 내에 있는 통행량과 여태 저장되어있는 통행량 중 높은 값을 결과값에 저장한다.
- 5. 2번부터 4번까지의 과정을 모든 도로에 대해서 탐색한 뒤, 결과값을 출력한다.

코드

# https://www.acmicpc.net/problem/19584
# 접근 방법
# 0. 주어진 도시(city)의 위치를 입력받고, 도로(road)에 대한 정보를 입력받는다. 단, 도로에 대한 정보를 입력받을 때는 각 도시의 y좌표를 입력받는다.
# 1. road를 오름차순으로 정렬한 뒤, 하나씩 탐색한다.
# 2. 만약 현재 탐색 중인 도로의 더 낮은 y좌표의 도시보다 최소힙의 0번째 인덱스의 값이 더 작다면 이를 반복적으로 삭제한다.
# 3. 각 도로를 탐색할 때 더 높은 y좌표를 기준으로 최소힙에 삽입한다.
# 4. 이후 힙 내에 있는 통행량과 여태 저장되어있는 통행량 중 높은 값을 결과값에 저장한다.
# 5. 2번부터 4번까지의 과정을 모든 도로에 대해서 탐색한 뒤, 결과값을 출력한다.
import sys, heapq
input = sys.stdin.readline

n, m = map(int, input().split())
city = [list(map(int, input().split())) for _ in range(n)]
road = []
for _ in range(m):
    u, v, c = map(int, input().split())
    y1, y2 = city[u-1][1], city[v-1][1]
    road.append(sorted([y1, y2]) + [c])

road.sort(key=lambda x: x[0])
min_heap = []
result = 0
score = 0
for u, v, c in road:
    while min_heap and min_heap[0][0] < u:
        x = heapq.heappop(min_heap)
        score -= x[1]
    heapq.heappush(min_heap, [v, c])
    score += c
    result = max(score, result)
print(result)