题目链接
https://www.acwing.com/problem/content/description/342/
题意
给定带权无向图，从1-n路径上第k+1大边权最小是多少？
思路
维护路径上的最大权/最小权很简单，更改dis定义即可，现在问题是如何记录第k+1大的边。第k+1大的边其实可以相当于在跑最短路过程中，无视了k条最大的边，这点在原题干中更易想出，题意抽象之后反而需要头脑转个弯。
第一次接触分层图，分层图是当对点有不同操作时建立多张图。在这道题中，我们可以建立k+1张图，对于边（u,v），我们除了在每一张图中连接，还要遍历将第i张图的u和第i+1张图的v；第i张图的v和第i+1张图的u相连，边权为0。在低层向高层“跑”权为0的边的时候，就相当于跳过了这条边的边权，那么跳过k次后会从第一层到达第k+1层，在这种情况下跑出的第k+1层终点的“距离”就是所求。
代码
#include<cstdio>
#include<iostream>
#include<iomanip>
#include<map>
#include<string>
#include<queue>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
//#define int long long
//#define double long double
using namespace std;typedef long long ll;const int maxn=1050*1050;const int maxe=20000+maxn; const int inf=0x3f3f3f3f;int n,m;int head[maxn];struct Edge{
int to;int next;int w;} edge[maxe];int cnt;int dis[maxn];void init(){
cnt=0;memset(head,-1,sizeof(head));return ;}inline void add(int u,int v,int w){
edge[cnt].next=head[u];edge[cnt].to=v;edge[cnt].w=w;head[u]=cnt;cnt++;}typedef pair<int,int> P;void dij(int start){
memset(dis,0x3f,sizeof(dis));priority_queue<P,vector<P>,greater<P> > q;dis[start]=0;q.push(P(0,start));while(!q.empty()){
P p=q.top(); q.pop();int v=p.second;if(dis[v]<p.first) continue;for(int i=head[v];~i;i=edge[i].next){
int tmp=edge[i].to;if(dis[tmp]>max(dis[v],edge[i].w)){
dis[tmp]=max(dis[v],edge[i].w);q.push(P(dis[tmp],tmp));}}}return ;}int main(){
IOSinit();int n,p,k;cin>>n>>p>>k;while(p--){
int u,v,w;cin>>u>>v>>w;add(u,v,w);add(v,u,w);for(int i=0;i<k;i++){
add(u+n*i,v+n*i+n,0);add(v+n*i,u+n*i+n,0);add(u+n*i+n,v+n*i+n,w);add(v+n*i+n,u+n*i+n,w);}}dij(1);if(dis[n+k*n]==inf)dis[n+k*n]=-1;cout<<dis[n+k*n]<<endl;return 0;}