萌新求助P1462 37分

崩溃中待解救

//P1462

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
queue<ll>q;
ll check(ll);
ll bsearch(ll l,ll r)
{
    while(l<r)
    {
        ll mid=(l+r)/2;
        if(!check(mid)) l=mid+1;
        else r=mid;
    }
    return l;
}
inline int read()
{
    register int ret=0,c=getchar();
    while(!isdigit(c))c=getchar();
    while(isdigit(c))ret=ret*10+c-'0',c=getchar();
    return ret;
}

struct ed
{
    int u,v,w;
};
int n,m,bb;
ll b[100010];
ll g[100010];
ll dis[100001];
bool vis[100010];
vector<ed>a[100001];
int main()
{
    int ck;
    n=read();
    m=read();
    bb=read();
    for(int i=1;i<=n;i++)
    {
        b[i]=read();
        if(b[i]>ck)
        {
            ck=b[i];
        }
    }
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        ed k,d;
        x=read();
        y=read();
        z=read();

        k.u=x;
        k.v=y;
        k.w=z;
        d.u=y;
        d.v=x;
        d.w=z;
        a[x].push_back(k);
        a[y].push_back(d);
    }
    if(!check(ck))
    {
        cout<<"AFK";
        return 0;
    }
    cout<<bsearch(1,ck);
    return 0;
}
ll check(ll x)
{
    memset(g,0,sizeof(g));
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)
    {
        if(b[i]>x)
        {
            g[i]=1;
        }
    }
    if(g[1]==1)
    {
        return 0;
    }
    q.push(1);
    dis[1]=0;
    vis[1]=1;
    while(!q.empty())
    {
        int c=q.front();
        q.pop();

        for(int i=0;i<a[c].size();i++)
        {

            if(g[a[c][i].v]==0&&vis[a[c][i].v]==0)
            {
                if(dis[i]+a[c][i].w<dis[a[c][i].v])
                {
                    dis[a[c][i].v]=dis[i]+a[c][i].w;
                    vis[a[c][i].v]=1;
                    q.push(a[c][i].v);
                }
            }
        }
        vis[c]=0;
    }

    if(dis[n]<bb)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}