题目描述
有 n 个区域,编号为 1,2,…,n。进入区域 i 时,飞机的高度必须不低于 ai,并且 a1=an=0。
区域之间有 m 条双向航线,第 j 条航线连接 uj 和 vj。保证所有区域从区域 1 出发都可达。
飞机从区域 1、高度 0 出发。每分钟可以沿一条航线飞到相邻区域,或者停留在原区域;与此同时,高度可以增加 1、减少 1 或保持不变。高度任何时候都不能小于 0,到达一个区域时必须满足该区域的最低高度要求。目标是在区域 n、高度 0 降落,求最短时间。
输入格式
第一行两个整数 n,m。
第二行 n 个整数 a1,a2,…,an。
接下来 m 行,每行两个整数 uj,vj,表示一条双向航线。
输出格式
输出一个整数,表示最短时间。
样例 1 输入
3 2
0 1 0
1 2
2 3
样例 1 输出
2
样例 1 解释
第一分钟沿航线从区域 1 到区域 2,同时将高度从 0 提升到 1;第二分钟从区域 2 到区域 3,同时将高度降回 0,所以最短时间为 2 分钟。
数据范围与子任务
所有数据满足 1≤n≤2×105、1≤m≤4×105、0≤ai≤108、a1=an=0,且 1≤uj,vj≤n、uj=vj。保证图连通。
本题采用捆绑计分。一个子任务中的全部测试点通过后,才能获得该子任务的分数。
| 子任务 |
分值 |
测试点 |
额外限制 |
| 1 |
22 |
1∼4 |
m=n−1,且每条边均为 (j,j+1) |
| 2 |
10 |
5∼6 |
n≤2000,m≤4000,且 ai≤2000 |
| 3 |
31 |
7∼11 |
n≤2000,m≤4000 |
| 4 |
37 |
12∼20 |
无额外限制 |