洛谷 P1462 通往奥格瑞玛的道路 二分 最短路

#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

using namespace std;

const long long INF=214748364666;

const int N=10000+2;

const int maxn=50000+3;

queue<int>Q;

long long d[N];

int inq[N];

int cost[N],A[N];

int head[N],to[maxn<<1],nex[maxn<<1],dis[maxn<<1];

int cnt,n,m,b,s,e,diff;

void add_edge(int u,int v,int c)

{

    nex[++cnt]=head[u],head[u]=cnt;

    to[cnt]=v,dis[cnt]=c;

}

void spfa()

{

    for(int i=1;i<=n;++i)d[i]=INF;

    if(cost[s]>diff)return;

    d[s]=0;inq[s]=1;Q.push(s);

    while(!Q.empty())

    {

        int u=Q.front();Q.pop();inq[u]=0;

        for(int v=head[u];v;v=nex[v])

        {

            if(d[u]+dis[v]<d[to[v]]&&cost[to[v]]<=diff)

            {

                d[to[v]]=d[u]+dis[v];

                if(!inq[to[v]])

                {

                    Q.push(to[v]);

                    inq[to[v]]=1;

                }

            }

        }

    }

}

int check(int t)

{

    diff=A[t];

    spfa();

    if(d[e]==INF||d[e]>b)return 0;

    return 1;

}

int main()

{

    //freopen("in.txt","r",stdin);

    scanf("%d%d%d",&n,&m,&b);

    s=1,e=n;

    for(int i=1;i<=n;++i)

    {

        scanf("%d",&cost[i]);

        A[i]=cost[i];

    }

    sort(A+1,A+1+n);

    for(int i=1;i<=m;++i)

    {

        int a,b,c;

        scanf("%d%d%d",&a,&b,&c);

        if(a==b)continue;

        add_edge(a,b,c);

        add_edge(b,a,c);

    }

    int L=1,R=n,ans=-1;

    while(L<=R)

    {

        int mid=(L+R)/2;

        if(check(mid))ans=mid,R=mid-1;

        else L=mid+1;

    }

    if(ans==-1)printf("AFK");

    else printf("%d",A[ans]);

    return 0;

}

　　

Code: