A23544. 有n个城市，编号为 1,2,3,...,n 。城市之间有 m 条双向的公路，每条公路连接着两个城市。从公路一端的城市走到另一端的城市，会损失力气。每次经过一个城市，都会被收取一定的过路费（包括起点和终点）。路上并没有收费站。小明从城市1出发，最终要到达城市 n 停下，而他的力气最多为 s ，出发时他的力气是满的。如果他到达目的地时所剩力气值变成负数，则他就无法到达城市 n ，且旅途中力气不会恢复…

有n个城市，编号为  1,2,3,...,n  。城市之间有  m  条双向的公路，每条公路连接着两个城市。从公路一端的城市走到另一端的城市，会损失力气。每次经过一个城市，都会被收取一定的过路费（包括起点和终点）。路上并没有收费站。小明从城市1出发，最终要到达城市 n 停下，而他的力气最多为 s ，出发时他的力气是满的。如果他到达目的地时所剩力气值变成负数，则他就无法到达城市  n ，且旅途中力气不会恢复。

小明希望在能到达城市 n 的情况下，让所经过的所有城市中**最多的一次收取的费用**的最小值尽可能小。若无法到达城市 n ，输出 NO  。

输入格式

第一行3个正整数  n,m,s  ，表示有  n(n＜=10000)  个城市、  m(m＜=50000)  条公路，小明满额力气为  s(s＜=le9)  。

第二行 n 个正整数，分别表示城市 1 到城市 n 需要交的费用。

接下来 m 行，每行3个正整数  x,y(1＜=x,y＜=n),z(z＜=1000)  ，表示城市 x 和城市 y 之间有一条双向路，往返都需要花费 z 的力气（可能有自环边）。

输出格式

输出一行，一个整数，表示小明能到达城市 n 时“交费最多的一次”的最小值；若无法到达，输出  NO  。

程序如下：

#include<bits/stdc++.h>
using namespace std;
const int N=10005;
const int M=50005;
const int maxlen=0x3f3f3f3f;
int n,m,s,tnt=0,head[N],dis[N];
bool in_que[N]; queue<int>q;
struct line{int v,w,Next;}line b[M*2];
void addedge(int x,int y,int z){
    b[++tnt].v=y; b[tnt].w=z; ① ; head[x]=tnt;
}
bool spfa(int money){
    while(!q.empty()) q.pop();
    memset(in_que,0,sizeof(in_que));
    for(int i=1;i<=n;i++) dis[i]=maxlen;
    dis[1]=0; in_que[1]=1; q.push(1);
    while(!q.empty()){
        int x=q.front(); q.pop(); in_que[x]=0;
        for(int i=head[x];i;i=b[i].Next){
            int y=b[i].v,z=b[i].w;
            if( ② ){
                dis[y]=dis[x]+z;
                if(!in_que[y]){ in_que[y]=1; q.push(y); }
            }
        }
    }
}
    ③  ;
}
int main(){
    scanf("%d%d%d",&n,&m,&s);
    int left=0,right=0;
    for(int i=1;i<=n;++i){
        scanf("%d",&f[i]); right=max(right,f[i]);
    }
    left=max(f[1],f[m]);
    for(int i=1;i<=m;++i){
        int x,y,z; scanf("%d%d%d",&x,&y,&z);
        if(x==y) continue;
        addedge(x,y,z); addedge(y,x,z);
    }
    if( ④ ){
        puts("NO"); return 0;
    }
    while(left<=right){
        int mid=(left+right)/2;
        if(spfa(mid)) right=mid-1;
        else left=mid+1;
    }
    printf("%d\n", ⑤ );
    return 0;
}

①处应该填（    ）。