若智方法求证伪（WA#8、9、10）

rt，没看题解之前觉得不需要最短路，二分答案check的时候直接从1号点开始dfs一遍，途中把不合要求的都剪枝，最终看第n号点是否访问到即可。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct edge{
    int to,c;
};
vector<edge> u[11451];
int n,m,b,f[11451],l,r,mid;//方便起见把mid定为dfs时的费用限制
bool vis[11451];
void dfs(int x,int hp){
    if(hp<0||f[x]>mid) return;
    vis[x]=1;
    for(int i=0;i<u[x].size();++i){
        int t=u[x][i].to,v=u[x][i].c;
        if(!vis[t]&&f[t]<=mid) dfs(t,hp-v);
    }
}
signed main(){
    cin>>n>>m>>b;
    for(int i=1;i<=n;++i){
        cin>>f[i];r=max(r,f[i]);
    } 
    for(int i=1;i<=m;++i){
        int x,y,z;
        cin>>x>>y>>z;
        edge p;p.to=y;p.c=z;
        u[x].push_back(p);
        p.to=x;
        u[y].push_back(p);
    }
    mid=0x7f7f7f7f;
    dfs(1,b);
    if(!vis[n]){
        cout<<"AFK";
        return 0;
    }
    while(l+1<r){
        memset(vis,0,sizeof(vis));
        mid=(l+r)/2;
        dfs(1,b);
        if(vis[n]) r=mid;
        else l=mid;
    }
    cout<<r;
    return 0;
}