题意

无向图中，可选择$k$条边将边权变为$0$，求最短路

数据范围：$2 \le n \le 10000,1 \le m \le 50000,0 \le k \le 10$

题解

分层图
每层内建原图，在层之间建边权为$0$的单向边，意为一次变化，因此共$k+1$层
为统计答案，由每一层的终点向超级汇点连一条权值为$0$的单向边

代码：

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
#define mp make_pair
typedef pair<int,int> pi;
const int N=10000+10;
const int M=50000+10;
int n,m,k,s,t,u,v,w;
int cnt;
int head[N*11],dis[N*11];
struct edge{
    int nxt,to,w;
} e[(M*4+N)*11];
inline void add(int u,int v,int w){
    e[++cnt]=edge{head[u],v,w};
    head[u]=cnt;
}
inline void Dijkstra(){
    memset(dis,0x3f,sizeof(dis));
    priority_queue<pi,vector<pi>,greater<pi> > Q;
    Q.push(mp(0,s));
    dis[s]=0;
    for(;!Q.empty();){
        pi p=Q.top();
        int u=p.second,d=p.first;
        Q.pop();
        if(d!=dis[u])
            continue;
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;
            if(dis[v]>dis[u]+e[i].w){
                dis[v]=dis[u]+e[i].w;
                Q.push(mp(dis[v],v));
            }
        }
    }
}
int main(){
    scanf("%d%d%d%d%d",&n,&m,&k,&s,&t);
    s++,t++;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&u,&v,&w);
        u++,v++;
        add(u,v,w);
        add(v,u,w);
        for(int j=1;j<=k;j++){
            add(u+n*j,v+n*j,w);
            add(v+n*j,u+n*j,w);
            add(u+n*(j-1),v+n*j,0);
            add(v+n*(j-1),u+n*j,0);
        }
    }
    for(int i=0;i<=k;i++)
        add(t+n*i,n*(k+1)+1,0);
    Dijkstra();
    printf("%d",dis[n*(k+1)+1]);
    return 0;
}