Eternality @ 2022-10-19 21:26:50
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6;
int n,m,b;
int to[N],nxt[N],h[N],w[N],tot;
int dis[N],v[N],ch[N];
void add(int x,int y,int z)
{
to[++tot]=y;
nxt[tot]=h[x];
h[x]=tot;
w[x]=z;
}
void SPFA(int maxx)
{
memset(dis,0x3f,sizeof dis);
memset(v,0,sizeof v);
queue<int> q;
if(ch[1]>maxx)return;
q.push(1);
dis[1]=0;
v[1]=1;
while(q.size())
{
int x=q.front();
q.pop();
v[x]=0;
for(int i=h[x];i;i=nxt[i])
{
int y=to[i];
int z=w[i];
if(ch[y]>maxx)continue;
if(dis[y]>dis[x]+z)
{
dis[y]=dis[x]+z;
if(!v[y])q.push(y),v[y]=1;
}
}
}
}
bool check(int x)
{
SPFA(x);
if(dis[n]>b)return false;
return true;
}
signed main()
{
scanf("%lld%lld%lld",&n,&m,&b);
for(int i=1;i<=n;i++)
{
scanf("%lld",&ch[i]);
}
for(int i=1;i<=m;i++)
{
int x,y,z;
scanf("%lld%lld%lld",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
int l=0,r=1e9,ans=-311;
while(l<=r)
{
int mid=l+r>>1;
if(check(mid))
{
ans=mid;
r=mid-1;
}else l=mid+1;
}
if(ans==-311)cout<<"AFK";
else cout<<ans;
return 0;
}
by Eternality @ 2022-10-19 21:49:31
@WeiFanbo 笑死我了对不起对不起
by Eternality @ 2022-10-19 21:51:25
@char_phi 笑死我了对不起哥
by WeiFanbo @ 2022-10-19 21:52:39
@Eternality 鹅鹅鹅对不起可还行