乐未殇 @ 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