代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#define RG register
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
const int N=1e3+10,M=1e4+10;
int n,p,k,cnt;
int dis[N],head[N];
bool vis[N];
struct nkl
{
int to,nex,pri;
}e[M<<1];
inline void add(int x,int y,int z)
{
e[++cnt].nex=head[x];
head[x]=cnt;
e[cnt].pri=z;
e[cnt].to=y;
}
inline bool check(int mid)
{
queue<int>q;
memset(dis,0x3f,sizeof(dis));
dis[1]=0;vis[1]=1;
q.push(1);
while(!q.empty())
{
int s;
int k=q.front();q.pop();
for (int i=head[k];i;i=e[i].nex)
{
int v=e[i].to;
if(e[i].pri>mid) s=dis[k]+1;
else s=dis[k];
if(s<dis[v])
{
dis[v]=s;
if(!vis[v])
{
vis[v]=1;
q.push(v);
}
}
}
vis[k]=0;
}
if(dis[n]<=k) return true;
return false;
}
int main()
{
scanf("%d%d%d",&n,&p,&k);
while(p--)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z),add(y,x,z);
}
int l=0,r=1e6,mid,ans=-1;
while(l<=r)
{
mid=(l+r)>>1;
if(check(mid)) r=mid-1,ans=mid;
else l=mid+1;
}
printf("%d\n",ans);
return 0;
}
/*
二分边的长度
*/