第八个点和第十一个点就是过不去。。。

#include<bits/stdc++.h>
using namespace std;
int n,m,b,pri[10010],head[10010],cnt,l,r,MAX;
struct pp{
    int data,nxt,c;
}rd[2*5*10000+10];
bool v[10010];
void add(int a,int b,int c){
    rd[++cnt].data=b;
    rd[cnt].nxt=head[a];
    rd[cnt].c=c;
    head[a]=cnt; 
}
bool bfs(int p){
    queue<pair<int,int> > q;
    memset(v,0,sizeof(v));
    if(p<pri[1])return false;
    v[1]=true;
    q.push(make_pair(1,b));
    while(q.size()){
        int x=q.front().first,y=q.front().second;
        q.pop();
        for(int i=head[x];i;i=rd[i].nxt){
            if(rd[i].c<=y&&pri[rd[i].data]<=p&&!v[rd[i].data]){
                q.push(make_pair(rd[i].data,y-rd[i].c));
                v[rd[i].data]=true;
                if(rd[i].data==n)return true;
            }
        }
    }
    return false;
}
int main(){
    //freopen("P1462_8.in","r",stdin);
    scanf("%d%d%d",&n,&m,&b);
    for(int i=1;i<=n;i++){
        scanf("%d",&pri[i]);
        MAX=max(MAX,pri[i]);
    }
    for(int i=1,a,b,c;i<=m;i++){
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);
    }
    r=MAX,l=pri[1];
    if(!bfs(1e9+10)){
        printf("AFK");
        return 0;
    }
    while(l<r){
        int mid=(l+r)>>1;
        if(!bfs(mid))l=mid+1;
        else r=mid;
    }
    printf("%d",l);
    return 0;
}