题目大意：给定一个 N 个顶点，M 条边的无向图，求一条从 1 号节点到 N 号节点之间的路径，使得第 K+1 大的边权最小，若 1 与 N 不连通，输出 -1。

最小化最大值一类的问题，采用二分答案即可，每次跑一遍 dij ，若边权大于二分的值，那么等效边权为1，否则边权为0，最后判断从 1 到 N 之间的最短路是否大于 K 即可。

代码如下

#include <cstdio>

#include <algorithm>

#include <memory.h>

#include <queue>

using namespace std;

const int maxv=1e3+10;

const int maxe=1e4+10;

struct node{

	int nxt,to,w;

	node(int x=0,int y=0,int z=0):nxt(x),to(y),w(z){}

}e[maxe<<1];

int tot=1,head[maxv];

int n,m,k,dis[maxv],mx;

bool vis[maxv];

void add_edge(int from,int to,int w){

	e[++tot]=node(head[from],to,w),head[from]=tot;

}

void read_and_parse(){

	scanf("%d%d%d",&n,&m,&k);

	for(int i=1,from,to,w;i<=m;i++){

		scanf("%d%d%d",&from,&to,&w);

		add_edge(from,to,w),add_edge(to,from,w);

		mx=max(mx,w);

	}

}

typedef pair<int,int> P;

bool right(int x){

	memset(dis,0x3f,sizeof(dis));

	memset(vis,0,sizeof(vis));

	priority_queue<P> q;

	dis[1]=0,q.push(make_pair(0,1));

	while(q.size()){

		int u=q.top().second;q.pop();

		if(vis[u])continue;

		if(u==n)break;

		vis[u]=1;

		for(int i=head[u];i;i=e[i].nxt){

			int v=e[i].to,w=(e[i].w>x?1:0);

			if(dis[v]>dis[u]+w){

				dis[v]=dis[u]+w;

				q.push(make_pair(-dis[v],v));

			}

		}

	}

	return dis[n]<=k;

}

bool dij(){

	memset(dis,0x3f,sizeof(dis));

	memset(vis,0,sizeof(vis));

	priority_queue<P> q;

	dis[1]=0,q.push(make_pair(0,1));

	while(q.size()){

		int u=q.top().second;q.pop();

		if(vis[u])continue;

		if(u==n)break;

		vis[u]=1;

		for(int i=head[u];i;i=e[i].nxt){

			int v=e[i].to,w=e[i].w;

			if(dis[v]>dis[u]+w){

				dis[v]=dis[u]+w;

				q.push(make_pair(-dis[v],v));

			}

		}

	}

	return dis[n]==0x3f3f3f3f;

}

void solve(){

	int l=0,r=mx;

	while(l<r){

		int mid=l+r>>1;

		if(right(mid))r=mid;

		else l=mid+1;

	}

	printf("%d\n",l);

}

int main(){

	read_and_parse();

	if(dij())return puts("-1"),0;

	solve();

	return 0;

}