粉刷匠 @ 2020-02-25 00:30:24
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int const inf=1000000010;
int n,m,b;
int f[10005];
int f1[10005];
int dis[10005];
int flag=1;
struct edge
{
int to,cost;
};
vector<edge>g[10005];
struct node
{
int u,d;
bool operator<(const node&a)const
{
return d>a.d;
}
};
inline bool djs(int x)
{
if(x<f1[1]||x<f1[n])
return false;
for(int i=1;i<=b;i++)
dis[i]=inf;
dis[1]=0;
priority_queue<node>Q;
node a={1,0};
Q.push(a);
while(!Q.empty())
{
node fr=Q.top();Q.pop();
int u=fr.u,d=fr.d;
if(d!=dis[u])continue;
if(u==n)continue;
for(int j=0;j<g[u].size();j++)
{
int tm=g[u][j].to;
if(f1[tm]>x)continue;
if(dis[u]+g[u][j].cost<dis[tm])
{
dis[tm]=dis[u]+g[u][j].cost;
Q.push((node){tm,dis[tm]});
}
}
}
return dis[n]<=b;
}
int main()
{
scanf("%d%d%d",&n,&m,&b);
for(int i=1;i<=n;i++)
{
scanf("%d",&f[i]);
f1[i]=f[i];
}
sort(f+1,f+1+n);
edge temp;
for(int i=1;i<=m;i++)
{
int x,y,cost;
scanf("%d%d%d",&x,&y,&cost);
temp.cost=cost;
temp.to=y;
g[x].push_back(temp);
temp.to=x;
g[y].push_back(temp);
}
if(!djs(f[n]))
{
printf("AFK\n");
return 0;
}
int l=1,r=n,mid;
int ans=f[n];
while(l<=r)
{
mid=(l+r)>>1;
if(djs(f[mid]))
{
ans=f[mid];
r=mid-1;
}
else l=mid+1;
}
printf("%d\n",ans);
/// printf("%d",ans);
return 0;
}
by 几何之舞丶 @ 2020-02-25 07:38:14
inf 开太大了.
dij的时候没有开个vis数组记录哪些边访问过,
by 粉刷匠 @ 2020-02-25 09:21:15
问题解决了谢谢