#CW44. 飞行计划(airplane)

飞行计划(airplane)

题目描述

有 nn 个区域,编号为 1,2,…,n1,2,\dots,n。进入区域 ii 时,飞机的高度必须不低于 aia_i,并且 a1=an=0a_1=a_n=0。

区域之间有 mm 条双向航线,第 jj 条航线连接 uju_j 和 vjv_j。保证所有区域从区域 11 出发都可达。

飞机从区域 11、高度 00 出发。每分钟可以沿一条航线飞到相邻区域,或者停留在原区域;与此同时,高度可以增加 11、减少 11 或保持不变。高度任何时候都不能小于 00,到达一个区域时必须满足该区域的最低高度要求。目标是在区域 nn、高度 00 降落,求最短时间。

输入格式

第一行两个整数 n,mn,m。

第二行 nn 个整数 a1,a2,…,ana_1,a_2,\dots,a_n。

接下来 mm 行,每行两个整数 uj,vju_j,v_j,表示一条双向航线。

输出格式

输出一个整数,表示最短时间。

样例 1 输入

3 2
0 1 0
1 2
2 3

样例 1 输出

2

样例 1 解释

第一分钟沿航线从区域 11 到区域 22,同时将高度从 00 提升到 11;第二分钟从区域 22 到区域 33,同时将高度降回 00,所以最短时间为 22 分钟。

数据范围与子任务

所有数据满足 1≤n≤2×1051\le n\le 2\times 10^5、1≤m≤4×1051\le m\le 4\times 10^5、0≤ai≤1080\le a_i\le 10^8、a1=an=0a_1=a_n=0,且 1≤uj,vj≤n1\le u_j,v_j\le n、uj≠vju_j\ne v_j。保证图连通。

本题采用捆绑计分。一个子任务中的全部测试点通过后,才能获得该子任务的分数。

子任务 分值 测试点 额外限制
1 22 1∼41\sim 4 m=n−1m=n-1,且每条边均为 (j,j+1)(j,j+1)
2 10 5∼65\sim 6 n≤2000n\le 2000,m≤4000m\le 4000,且 ai≤2000a_i\le 2000
3 31 7∼117\sim 11 n≤2000n\le 2000,m≤4000m\le 4000
4 37 12∼2012\sim 20 无额外限制