寒冰大大 @ 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