( ext{Solution:})
关于分层图：
一般用于处理：给你(k)次机会对边权进行修改的最短路问题。
算法流程：
-
建立出(k)层图，对应进行(k)次操作后的局面。
-
不同图之间建立边，即表示从当前局面进行一次操作转移到下一个局面。
由分层对图的边和点较多，所以开空间的时候一定要精确计算，避免空间爆炸和运行时错误。
对于本题：
这题的操作就是把一条边的边权改为(0).于是，类似地，我们建立(k)层图，并对每一条边向下一层连边，构造出分层图跑即可。
关于边数：(E=(4k+2)*m)约为(2.1*10^6.)于是我们直接把边开到(2.5*10^6)即可。
对于点的空间不必要开这么大，只是笔者没有改而已……
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2.5e6+10;
int head[MAXN],tot,n,m,dis[MAXN];
struct E{int nxt,to,dis;}e[MAXN];
int vis[MAXN],k,S,T,ans;
inline void add(int x,int y,int w){e[++tot]=(E){head[x],y,w};head[x]=tot;}
struct Q{
int dis,pos;
bool operator<(const Q&x)const{
return x.dis<dis;
}
};
priority_queue<Q>q;
void dijkstra(int s){
memset(dis,0x3f3f3f3f,sizeof dis);
dis[s]=0;q.push((Q){dis[s],s});
while(!q.empty()){
Q tmp=q.top();q.pop();
int x=tmp.pos;
if(vis[x])continue;
vis[x]=1;
for(int i=head[x];i;i=e[i].nxt){
int j=e[i].to;
if(dis[j]>dis[x]+e[i].dis){
dis[j]=dis[x]+e[i].dis;
if(!vis[j])q.push((Q){dis[j],j});
}
}
}
}
int main(){
scanf("%d%d%d",&n,&m,&k);
scanf("%d%d",&S,&T);
for(int i=1;i<=m;++i){
int u,v,c;
scanf("%d%d%d",&u,&v,&c);
add(u,v,c);add(v,u,c);
for(int j=1;j<=k;++j){
add(u+(j-1)*n,v+j*n,0);
add(v+(j-1)*n,u+j*n,0);
add(u+j*n,v+j*n,c);
add(v+j*n,u+j*n,c);
}
}
dijkstra(S);ans=(1<<30);
for(int i=0;i<=k;++i)ans=min(ans,dis[T+i*n]);
printf("%d
",ans);
return 0;
}