题意：
给定一张无向图，起点和终点，可以选择其中
k
k
k条边将其边权改为0,求从起点到终点的最小代价
数据范围&性质：
1
≤
n
≤
1
0
4
,
q
≤
m
≤
5
×
1
0
4
,
1
≤
k
≤
10
1\le n\le 10^4,q\le m\le 5\times 10^4,1\le k\le 10
1≤n≤104,q≤m≤5×104,1≤k≤10
分析：
没什么好说的，就是分层图裸题，只是我一直不知道有这么一种做法
简单说就是建
k
+
1
k+1
k+1张图，每个点除了和自身这张图的对应点，还和下一张图的对应点连一条边权为0的边，然后有第一张图的起点，向第
k
+
1
k+1
k+1张图的终点跑一遍最短路
代码：
#include<bits/stdc++.h>
#define mk(x,y) make_pair(x,y)
using namespace std
;
namespace zzc
{
const int maxm
= 5e4+5;
const int maxn
= 2e4+5;
int head
[maxn
*10];
long long dis
[maxn
*10];
bool vis
[maxn
*10];
int n
,cnt
=0,m
,k
,st
,ed
;
struct edge
{
int to
,nxt
,val
;
}e
[3000005];
void add(int u
,int v
,int w
)
{
e
[++cnt
].to
=v
;
e
[cnt
].val
=w
;
e
[cnt
].nxt
=head
[u
];
head
[u
]=cnt
;
}
void dijkstra()
{
memset(dis
,0x3f,sizeof(dis
));
dis
[st
]=0;
priority_queue
<pair
<long long,int> > q
;
q
.push(mk(0,st
));
while(!q
.empty())
{
int u
=q
.top().second
;
q
.pop();
if(!vis
[u
])
{
vis
[u
]=true;
for(int i
=head
[u
];i
;i
=e
[i
].nxt
)
{
int v
=e
[i
].to
;
if(dis
[v
]>dis
[u
]+e
[i
].val
)
{
dis
[v
]=dis
[u
]+e
[i
].val
;
q
.push(mk(-dis
[v
],v
));
}
}
}
}
}
void work()
{
int a
,b
,c
;
scanf("%d%d%d%d%d",&n
,&m
,&k
,&st
,&ed
);
for(int i
=1;i
<=m
;i
++)
{
scanf("%d%d%d",&a
,&b
,&c
);
add(a
,b
,c
);
add(b
,a
,c
);
for(int j
=1;j
<=k
;j
++)
{
add(a
+(j
-1)*n
,b
+j
*n
,0);
add(b
+(j
-1)*n
,a
+j
*n
,0);
add(a
+j
*n
,b
+j
*n
,c
);
add(b
+j
*n
,a
+j
*n
,c
);
}
}
for(int i
=1;i
<=k
;i
++)
{
add(ed
+(i
-1)*n
,ed
+i
*n
,0);
}
dijkstra();
printf("%lld\n",dis
[ed
+k
*n
]);
}
}
int main()
{
zzc
::work();
return 0;
}
