为什么10RE???

P1462 通往奥格瑞玛的道路

乐未殇 @ 2019-10-05 21:44:58

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
/*inline void fread(long long &x)
{
    char ch=getchar();
    int s=0,w=1;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        s=(s<<3)+(s<<1)+ch-'0';
        ch=getchar();
    }
    x=s*w;
}*/

long long n,m,h;
long long maxn;
long long l,r,mid;
long long f[150000],g[150000],w[150000],first[150000],ne[150000];
long long dis[150000],vis[150000];
long long cnt;
void add(long long a,long long b,long long c)
{
    cnt++;
    f[cnt]=a;
    g[cnt]=b;
    w[cnt]=c;
    ne[cnt]=first[f[cnt]];
    first[f[cnt]]=cnt;
}
queue<long long >q;
long long fy[1000000];
inline bool spfa(int mid)
{
    if(fy[1]>mid) return false;
    long long x=1;
    for(long long i=1;i<=maxn+1;i++)
    {
        vis[i]=0;
        dis[i]=99999999;
    }
    q.push(x);
    dis[x]=0;
    vis[x]=1;
    while(!q.empty())
    {
        int start=q.front();
        q.pop();vis[start]=0;
        int u=first[start];
        while(u!=-1)
        {
            if(dis[g[u]]>dis[f[u]]+w[u]&&fy[g[u]]<=mid)
            {
                dis[g[u]]=dis[f[u]]+w[u];
                if(!vis[g[u]])
                {
                    vis[g[u]]=1;
                    q.push(g[u]);
                }
            }
            u=ne[u];
        }
    }
    if(dis[n]>h)
    {
        return false;
    }
    else return true;
}

int main()
{
    scanf("%lld%lld%lld",&n,&m,&h);
/*  fread(n);
    fread(m);
    fread(h);*/
    for(long long i=1;i<=n;i++)
    {
        first[i]=-1;
    }
    for(long long i=1;i<=n;i++)
    {
        scanf("%lld",&fy[i]);
        //fread(fy[i]);     
        maxn=max(maxn,fy[i]);
    }
    for(long long i=1;i<=m;i++)
    {
        long long a,b,c;
        scanf("%lld%lld%lld",&a,&b,&c);
    /*  fread(a);
        fread(b);
        fread(c);*/
        add(a,b,c);
        add(b,a,c);
    }
    if(spfa(99999999)==false)
    {
        printf("AFK\n");
        return 0;
    } 
    l=0,r=maxn;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(spfa(mid)==true)
        {
            r=mid-1;
        }
        else
        {
            l=mid+1;
        }
    }
    cout<<l<<endl;
}

求大佬解释


by tidongCrazy @ 2019-10-05 22:05:37


|