#include <cstdio> #include <queue> #include <cstring> using namespace std; const int N = 1001; const int M = 20001; int n,m,k; struct EDGE{ int next; int to; int len; }edge[M]; struct NODE{ int pos; int free; }; queue <NODE> q; int head[N]; bool vis[N][N]; int cnt = 0; int dist[N][N]; void add_edge(int x,int y,int len) { edge[++cnt].to = y; edge[cnt].len = len; edge[cnt].next = head[x]; head[x] = cnt; } void spfa() { memset(dist,0x3f,sizeof dist); q.push((NODE){1,0}); vis[1][0] = 1; dist[1][0] = 0; while(!q.empty()) { NODE top = q.front(); q.pop(); vis[top.pos][top.free] = 0; for(int i=head[top.pos];i;i=edge[i].next) { int y = edge[i].to; if(max(dist[top.pos][top.free],edge[i].len) < dist[y][top.free]) { dist[y][top.free] = max(dist[top.pos][top.free],edge[i].len); if(!vis[y][top.free]) { vis[y][top.free] = 1; q.push((NODE){y,top.free}); } }

if(top.free < k && dist[y][top.free+1] > dist[top.pos][top.free])
		{
			dist[y][top.free+1] = dist[top.pos][top.free];
			if(!vis[y][top.free+1])
			{
				q.push((NODE){y,top.free+1});
				vis[y][top.free+1] = 1;
			}
		}
	}
}

}

// dist[next][top.free] --> max(dist[top.pos][top.free] , edge[i].len int main() { scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=m;i++) { int x,y,l; scanf("%d%d%d",&x,&y,&l); add_edge(x,y,l); //无向图加条边 add_edge(y,x,l); } spfa(); if(dist[n][k] == 0x3f3f3f3f) printf("-1\n"); else printf("%d\n",dist[n][k]); }

C++ :

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
const int N = 1001;
const int M = 20001;
int n,m,k;
struct EDGE{
	int next;
	int to;
	int len;
}edge[M];
struct NODE{
	int pos;
	int free;
};
queue <NODE> q;
int head[N];
bool vis[N][N];
int cnt = 0;
int dist[N][N];
void add_edge(int x,int y,int len)
{
	edge[++cnt].to = y;
	edge[cnt].len = len;
	edge[cnt].next = head[x];
	head[x] = cnt;
}
void spfa()
{
	memset(dist,0x3f,sizeof dist);
	q.push((NODE){1,0});
	vis[1][0] = 1;
	dist[1][0] = 0;
	while(!q.empty())
	{
		NODE top = q.front();
		q.pop();
		vis[top.pos][top.free] = 0;
		for(int i=head[top.pos];i;i=edge[i].next)
		{
			int y = edge[i].to;
			if(max(dist[top.pos][top.free],edge[i].len) < dist[y][top.free])
			{
				dist[y][top.free] = max(dist[top.pos][top.free],edge[i].len);
				if(!vis[y][top.free])
				{
					vis[y][top.free] = 1;
					q.push((NODE){y,top.free});
				}
			}

			if(top.free < k && dist[y][top.free+1] > dist[top.pos][top.free])
			{
				dist[y][top.free+1] = dist[top.pos][top.free];
				if(!vis[y][top.free+1])
				{
					q.push((NODE){y,top.free+1});
					vis[y][top.free+1] = 1;
				}
			}
		}
	}

}

// dist[next][top.free] --> max(dist[top.pos][top.free] , edge[i].len
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=m;i++)
	{
		int x,y,l;
		scanf("%d%d%d",&x,&y,&l);
		add_edge(x,y,l);   //无向图加条边
		add_edge(y,x,l);
	}
	spfa();
	if(dist[n][k] == 0x3f3f3f3f)
		printf("-1\n");
	else
		printf("%d\n",dist[n][k]);
}