63分求助

P1462 通往奥格瑞玛的道路

寒冰大大 @ 2018-10-26 14:01:07

#include<iostream>
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include <utility>
using namespace std;
int head[100806];
int size;
struct edge{
    int next,to,dis;
};
edge E[500500];
int n,m,canbe;
int d[100806],cost[100806],life;
int v[100806];
void addedge(int next,int to,int dis)
{
    E[++size].next=head[next];
    E[size].to=to;
    E[size].dis=dis;
    head[next]=size;
}
void dij(int s,int maxcost)
{
    memset(d,0x3f,sizeof(d));
    canbe=0;
    memset(v,0,sizeof(v));
    priority_queue<pair<int,int> > q;
    d[s]=0;
    q.push(make_pair(0,s));
    while(!q.empty())
    {
        int t=q.top().second;
        q.pop();
        if(v[t])continue;
            v[t]=1;
        for(int i=head[t];i;i=E[i].next)
        {
            int k=E[i].dis;
            int j=E[i].to;
            if(d[j]>d[t]+k&&cost[j]<=maxcost)
            {
                if(j==n) canbe=1;
                d[j]=d[t]+k;
                q.push(make_pair(-d[j],j));
            }
        }
    }
}
int main()
{
    cin>>n>>m>>life;
    int i,j;
    int maxn=-1;
    for(i=1;i<=n;i++)
    {
        scanf("%ld ",&cost[i]);
        if(cost[i]>maxn)
        maxn=cost[i];
    }
    for(i=1;i<=m;i++)
    {
        int tx,ty,tdis;
        scanf("%d %d %d",&tx,&ty,&tdis);
        if(tx==ty) continue;
        addedge(tx,ty,tdis);
        addedge(ty,tx,tdis);
    }
    dij(1,maxn);
    if(d[n]>life||!canbe) {
        cout<<"AFK";
        return 0;
    }
    int mid,l=1,r=maxn;
    while(l<=r)
    {
        mid=(l+r)/2;
        dij(1,mid);
        if(d[n]<=life) r=mid-1;
        else l=mid+1;
    }
    cout<<mid<<endl;
    return 0;
}

by zzqDeco @ 2018-10-26 14:02:37

e


|