頁面無法載入？點擊這裡可能會修復。
Placeholder

#5923

비행 1s 1024MB

問題

1 부터 n까지 번호가 붙은 n개의 비행 가능한 지역이 있다.

각 지역은 특수한 지형 때문에 i번 지역을 비행하려면 최소 고도 a[i]를 지켜야 한다.

또한 탁월풍(어느 한 지역에서 일정 기간 동안 가장 우세하게 나타나는 바람)의 영향으로 특정 지역 쌍들 사이만 비행할 수 있다.

1부터 m까지 번호가 매겨진 m개의 지역 쌍이 있다. j번째 쌍은 u[j]와 v[j]를 가지는데 이는 u[j]지역과 v[j]지역을 양방향으로 다닐 수 있다는 의미이다.

이 쌍들을 이용하여 어떤 지역에서 출발하든 다른 모든 지역으로 도착할 수 있음이 보장된다.

처음에는 1번 지역의 고도 0에 있으며, n번 지역으로 이동하고 싶으며, n번 지역의 고도 0으로 착륙해야 한다.

1분 이 경과하면 현재 지역에 머물거나 다른 지역으로 떠날 수 있고 동시에 고도를 1증가하거나 1감소하거나 유지할 수 있다.

그러나 지역에 도착하면 고도는 최소 고도 이상이어야 한다. 1번 지역에서 이륙하여 n번 지역에 착륙하는 최소 시간을 구하라.


輸入

첫 줄에 n과 m이 공백을 구분으로 주어진다.

다음 줄에 n개의 a[1],a[2],\cdots,a[n] 이 주어진다.

다음 m개의 줄에 숫자 쌍이 주어지며 j번째 줄에 u[j]와 v[j]가 주어진다.

[제약 조건]

1 \le n \le 200,000

1 \le m \le 400,000

0 \le a[i] \le 10^8

a[1] = a[n] = 0

1 \le u[j], v[j] \le n, u[j] \neq v[j]


輸出

n번 지역에 착륙하기 위한 최소 시간을 출력하라.


子任務

編號 分數 條件
#122分

m=n-1, u[j]=j, v[j]=j+1

#210分

n \le 2000, m \le 4000, a[i] \le 2000

#331分

n \le 2000, m \le 4000

#437分

추가 제약 조건 없음.


範例 #1

3 2
0 2 0
1 2
2 3
4

1번 지역에서 3번 지역으로 4분만에 도달 할 수 있다.

1분차에는 1번 지역에서 머물면서 고도를 0에서 1로 높인다.

2분차에는 1번 지역에서 2번 지역으로 이동하면서 고도를 1에서 2로 높인다.

3분차에는 2번 지역에서 3번 지역으로 이동하면서 고도를 2에서 1로 낮춘다.

4분차에는 3번 지역에서 머물면서 고도를 1에서 0으로 낮춘다.


範例 #2

11 12
0 0 0 0 0 0 2 2 1 5 0
1 2
2 3
3 4
4 5
5 6
6 11
1 7
7 8
8 9
9 11
1 10
10 11
5

1번 지역에서 11번 지역으로 5분만에 도달 할 수 있다.

1분차에는 1번 지역에서 머물면서 고도를 0에서 1로 높인다.

2분차에는 1번 지역에서 7번 지역으로 이동하면서 고도를 1에서 2로 높인다.

3분차에는 7번 지역에서 8번 지역으로 이동하면서 고도를 유지한다.

4분차에는 8번 지역에서 9번 지역으로 이동하면서 고도 2에서 1로 낮춘다.

5분차에는 9번 지역에서 11번 지역으로 이동하면서 고도를 1에서 0으로 낮춘다.


來源

NOI 2023 3번 (데이터 추가 : eva)
需要登入才能撰寫程式碼。