대평원

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

요약
서로 겹치지 않는 축에 평행한 직사각형들과 km당 이동 시간이 주어질 때, 축에 평행하게만 움직여 시작점에서 도착점까지 가는 최소 시간을 구한다.
난이도

어려움10점 중 8점

유형
그래프, 최단 경로, 기하, 정렬
정답자
아직 제출이 없습니다

문제

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

구릉지는 xx축과 yy축에 평행한 변으로 구성된 직사각형 모양이며 직사각형마다 11km를 이동하는 데 걸리는 시간이 주어진다. 이 이동시간은 직사각형의 내부에만 적용되고 변에는 적용되지 않는다. 또한 서로 다른 두 직사각형은 겹치지 않으며 시작점, 도착점, 그리고 서로 다른 직사각형들의 꼭지점 xx좌표들은 모두 정수이며 겹치지 않는다. yy좌표들도 마찬가지로 모두 정수이며 겹치지 않는다. 시작점과 도착점은 항상 직사각형의 외부에 존재한다.

위 예제는 km 단위 좌표에 km당 이동 시간이 200200분인 직사각형-왼쪽 아래 좌표가 (0,1)(0,1)이고 오른쪽-위 좌표가 (5,2)(5,2)과 km당 이동 시간이 1,0001\\,000분인 직사각형-왼쪽 아래 좌표가 (4,3)(4,3)이 고 오른쪽-위 좌표가 (9,4)(9,4)를 표시한 것이다. 시작점이 A이고 도착점이 B인 경우와 시작점이 C이고 도착점이 D인 경우의 최단시간 경로가 표시되어 있으며 각각 최단시간은 700700분과 1,0001\\,000분이다.

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

  • 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까지의 최단시간을 구하여 return 한다.

제한

  • 1≤N≤100,0001 \le N \le 100\\,000
  • 100≤w≤108100 \le w \le 10^8
  • 0≤x,y≤1080 \le x, y \le 10^8 (xx, yy는 시작점, 도착점, 또는 직사각형의 꼭지점의 좌표값)
  • NN, ww, xx, yy는 모두 정수

예제2

  1. 예제 1

    입력
    3 2 14 5 1
4 6 6 10 1000
0 7 3 9 200
1 2 8 5 150
    예상 출력
    1750

  2. 예제 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
    예상 출력
    11770