하늘길 걷기

케난은 바쿠의 큰길 한쪽에 늘어선 건물과 구름다리의 설계도를 그렸다. 건물은 $0$번부터 $n-1$번까지, 구름다리는 $0$번부터 $m-1$번까지 번호가 붙는다. 설계도에서 건물은 수직 선분이고 구름다리는 수평 선분이다.

건물 $i$의 바닥은 $(x[i],0)$이고 높이는 $h[i]$다. 따라서 건물은 $(x[i],0)$과 $(x[i],h[i])$를 잇는 선분이다.

구름다리 $j$는 건물 $l[j]$와 $r[j]$에 끝점을 두고 양의 $y$좌표 $y[j]$를 갖는다. 즉, $(x[l[j]],y[j])$와 $(x[r[j]],y[j])$를 잇는다.

구름다리와 건물이 한 점을 공유하면 서로 교차한다. 구름다리는 양 끝의 두 건물뿐 아니라 그 사이의 다른 건물과도 교차할 수 있다.

건물과 구름다리 위로만 걸을 수 있을 때 건물 $s$의 바닥에서 건물 $g$의 바닥까지 가는 최단 거리를 구하여라. $y=0$인 지면을 따라 걷는 것은 허용되지 않는다. 교차점에서는 건물과 구름다리 사이를 이동할 수 있고, 두 구름다리의 끝점이 같으면 한 구름다리에서 다른 구름다리로 이동할 수 있다. 경로가 없으면 이를 판별해야 한다.

구현 세부 사항

각 테스트 케이스마다 다음 함수가 한 번 호출된다.

long long min_distance(vector<int> x, vector<int> h,
                       vector<int> l, vector<int> r, vector<int> y,
                       int s, int g)

• $x$, $h$: 길이가 $n$인 정수 배열
• $l$, $r$, $y$: 길이가 $m$인 정수 배열
• $s$, $g$: 시작 건물과 도착 건물
• 경로가 있으면 최단 거리를, 없으면 $-1$을 반환해야 한다.

예제

예제 1

min_distance([0, 3, 5, 7, 10, 12, 14],
             [8, 7, 9, 7, 6, 6, 9],
             [0, 0, 0, 2, 2, 3, 4],
             [1, 2, 6, 3, 6, 4, 6],
             [1, 6, 8, 1, 7, 2, 5],
             1, 5)

정답은 $27$이다.

예제 2

min_distance([0, 4, 5, 6, 9],
             [6, 6, 6, 6, 6],
             [3, 1, 0],
             [4, 3, 2],
             [1, 3, 6],
             0, 4)

정답은 $21$이다.

제한

• $1 \leq n,m \leq 100\,000$
• $0 \leq x[0] < x[1] < \cdots < x[n-1] \leq 10^9$
• 모든 $i$에 대해 $1 \leq h[i] \leq 10^9$
• 모든 $j$에 대해 $0 \leq l[j] < r[j] \leq n-1$
• 모든 $j$에 대해 $1 \leq y[j] \leq \min(h[l[j]],h[r[j]])$
• $0 \leq s,g \leq n-1$이고 $s \neq g$
• 두 구름다리는 끝점이 아닌 곳에서는 공통점을 갖지 않는다.

부분 문제

1. (10점) $n,m \leq 50$
2. (14점) 각 구름다리는 최대 $10$개 건물과 교차한다.
3. (15점) $s=0$, $g=n-1$이고 모든 건물의 높이가 같다.
4. (18점) $s=0$, $g=n-1$
5. (43점) 추가 제한이 없다.

• 첫째 줄: $n\;m$
• 이어지는 $n$개 줄의 $i$번째 줄: $x[i]\;h[i]$
• 이어지는 $m$개 줄의 $j$번째 줄: $l[j]\;r[j]\;y[j]$
• 마지막 줄: $s\;g$

• min_distance의 반환 값을 한 줄에 출력한다.