대평원

시간 제한3초메모리 제한1024 MB

요약

축에 평행하게만 움직이는 개미가 각 사각형 내부에서 1km당 주어진 시간이 걸릴 때, 시작점에서 도착점까지 가는 최단 시간을 구합니다.

난이도: 어려움10점 중 8점
유형: 최단 경로, 그래프, 기하, 정렬
정답자: 아직 제출이 없습니다

문제

$1$ km를 $100$ 분에 이동하는 개미가 대평원 위의 시작점에서 도착점으로 이동하려고 한다. 단, $x$ 축과 $y$ 축에 평행하게 이동해야 하고 구릉지에서는 이동 시간이 늘어날 수 있다. 시작점, 도착점, 구릉지들, 그리고 구릉지마다 1km를 이동하는 데 걸리는 시간이 주어졌을 때, 이 개미가 시작점에서 도착점까지 가장 빠르게 이동할 수 있는 시간을 계산하라.

구릉지는 $x$ 축과 $y$ 축에 평행한 변으로 이루어진 직사각형이며, 직사각형마다 1km를 이동하는 데 걸리는 시간이 주어진다. 이 이동 시간은 직사각형의 내부에만 적용되고 변에는 적용되지 않는다. 서로 다른 두 직사각형은 겹치지 않는다. 시작점, 도착점, 그리고 서로 다른 직사각형들의 꼭짓점 $x$ 좌표는 모두 정수이며 서로 같지 않다. $y$ 좌표도 마찬가지이다. 시작점과 도착점은 항상 직사각형의 바깥에 있다.

구현

여러분은 다음 함수를 구현해야 한다.

long long shortest_path(pair<int, int> src, pair<int, int> dst, vector<pair<int, int>> p1, vector<pair<int, int>> p2, vector<int> w); 단 한 번 호출되는 함수이다. src는 시작점, dst는 도착점이다. 각 직사각형의 왼쪽 아래 점은 p1에, 오른쪽 위 점은 p2에 주어진다. 이 값들을 이용해 src에서 dst까지의 최단시간을 구해서 반환한다.

제한

$1 \le N \le 100\,000$
$100 \le w \le 10^8$
$0 \le x, y \le 10^8$ ( $x$ , $y$ 는 시작점, 도착점, 또는 직사각형의 꼭짓점의 좌표값)
$N$ , $w$ , $x$ , $y$ 는 모두 정수

예제2

예제 1

입력

3 2 14 5 1
4 6 6 10 1000
0 7 3 9 200
1 2 8 5 150

예상 출력

예제 2

입력

13 0 38 100 25
1 39 2 46 190
9 78 10 80 230
20 42 21 89 170
27 26 28 68 170
35 41 36 99 270
43 36 44 63 280
51 15 52 27 150
57 14 58 29 190
64 2 65 90 160
75 33 76 35 290
78 5 79 100 290
88 28 89 40 190
94 7 95 50 250

예상 출력