分层图可以处理从图中选取k条边使其边权变为0，求最短路
Description
在你的强力援助下，PCY 成功完成了之前的所有任务，他觉得，现在正是出去浪的大好时光。于是，他来到高速公路上，找到一辆摩的前往几千公里以外他心仪的那家黄焖鸡米饭。
由于 PCY 的品味异于常人，途经几百个城市的黄焖鸡米饭他都不屑一顾，他只愿意前往他心中最好的那家，但是为了一碗二十块钱的黄焖鸡米饭，他不愿意花上几千块的路费，他希望路费尽量少。高速路上的警察叔叔被他的行为所打动，于是在多方协调下，最多 K 条城市之间的高速收费站愿意免费为 PCY 放行（可以任意选择）。
显然，PCY 已经筋疲力尽，不想再动用自己的数学天才来计算他可以花费的最小路费，因此他希望你可以帮他最后一次，他说他可以请你吃大碗的黄焖鸡米饭，还可以加一瓶豆奶。
现在给你 N 个城市（编号为 0 … N - 1 ）， M 条道路，和每条高速公路的花费 Wi ，以及题目所描述的 K。PCY 想从城市 S 到城市 T， 因为他对 T 城市的黄焖鸡米饭情有独钟。Input (Prefix.in)
第一行，三个整数 N，M，K ，如题意所描述
第二行，两个整数 S，T ，代表出发城市和目标城市编号
接下来 M 行，每行三个整数 X，Y，W ，代表 X 和 Y 城市之间的高速公路收费为 W 元Output (Prefix.out)
共一行，输出一个整数，代表 PCY 最少需要花费的路费。
借鉴Kigo的想法，分层图就是K层平行宇宙,每一层里有一个完整的图，但平行宇宙之间有互相连通的虫洞，可以从一个平行宇宙中的一个点瞬间到达下一个平行宇宙(原先x->y 边权为w，现在x->y’边权为0)，然而虫洞是单向的，你不能回到上一个平行宇宙，只能向下一个平行宇宙走；最终，每一个平行宇宙都有同样的目的地，看到哪一个目的地最省钱
在这里，K层分层图说明最多有K条0边权的路可以走，建图后跑最短路即可
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#define MAXM 5000000
using namespace std; int s,t,n,m,k; inline int Read(){
int x=;char ch=getchar();
while(ch<'' || ch>''){ch=getchar();}
while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}
return x;
} struct E{
int next,to,v;
}edge[MAXM];
int head[MAXM];int edge_num;
int dis[MAXM]; void addedge(int x,int y,int z){
edge[++edge_num].next=head[x];
edge[edge_num].to=y;
edge[edge_num].v=z;
head[x]=edge_num;
} int que[MAXM];int front,tail;
bool inque[MAXM]; void PUSH(int x){
tail++;
if(tail==) tail=;
que[tail]=x;inque[x]=;
} int POP(){
front++;
if(front==) front=;
int t=que[front];
inque[t]=;
return t;
} void SPFA(int x){
memset(dis,0x7f,sizeof(dis));
PUSH(x);
dis[x]=;
while(front<tail){
int fro=POP();
int i;
for(i=head[fro];i;i=edge[i].next){
if(dis[edge[i].to]>dis[fro]+edge[i].v){
dis[edge[i].to]=dis[fro]+edge[i].v;
if(!inque[edge[i].to]){
PUSH(edge[i].to);
}
}
}
}
} void solve(){
SPFA(s);
int i;
int ans=0x7fffffff;
for(i=;i<=k;i++){
ans=min(ans,dis[t+n*i]);
}
printf("%d\n",ans);
} int main(){
freopen("Motor.in","r",stdin);
freopen("Motor.out","w",stdout);
n=Read();m=Read();k=Read();s=Read();t=Read();
int i;
if(k==){
for(i=;i<=m;i++){
int a=Read();int b=Read();int c=Read();
int j;
addedge(a,b,c);
addedge(b,a,c);
}
SPFA(s);
printf("%d\n",dis[t]);
return ;
}
for(i=;i<=m;i++){
int a=Read();int b=Read();int c=Read();
int j;
for(j=;j<=k;j++){
addedge(a+n*j,b+n*j,c);
addedge(b+n*j,a+n*j,c);
if(j<k){
addedge(a+n*j,b+n*(j+),);
addedge(b+n*j,a+n*(j+),);
}
}
}
solve();
return ;
}
不推荐
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int maxn = ;
const int maxm = ;
const int inf = 0x3f3f3f3f; void Read(int& x)
{
char t = getchar();
while (t < '' || t > '') t = getchar();
x = ;
while (t >= '' && t <= '') {
x = x * + t - '';
t = getchar();
}
} struct Heap
{
int place[maxn], val[maxn], idx[maxn], node_cn; Heap() { node_cn = ; memset(place, , sizeof(place)); } inline void Swap(int x, int y)
{
swap(place[idx[x]], place[idx[y]]);
swap(val[x], val[y]);
swap(idx[x], idx[y]);
} void adjustup(int x)
{
while (x > ) {
if (val[x] < val[x >> ]) {
Swap(x, x >> );
x >>= ;
} else {
break;
}
}
} void adjustdown(int x)
{
int v;
while ((x << ) <= node_cn) {
v = x << ;
if (v + <= node_cn && val[v + ] < val[v]) v = v + ;
if (val[x] > val[v]) {
Swap(x, v);
x = v;
} else {
break;
}
}
} void insert(int id, int v)
{
if (place[id]) {
val[place[id]] = -inf;
adjustup(place[id]);
val[] = v;
adjustdown();
} else {
node_cn ++;
val[node_cn] = v, idx[node_cn] = id, place[id] = node_cn;
adjustup(node_cn);
} } void pop()
{
Swap(, node_cn);
node_cn --;
adjustdown();
}
}; int fst[maxn], edge_cn = ;
int u[maxm], v[maxm], w[maxm], nxt[maxm]; void addedge(int x, int y, int _w)
{
edge_cn ++;
u[edge_cn] = x, v[edge_cn] = y, w[edge_cn] = _w;
nxt[edge_cn] = fst[x];
fst[x] = edge_cn;
} int n, m, k, s, t;
int dis[maxn]; void input()
{
int x, y, z;
memset(fst, -, sizeof(fst));
Read(n), Read(m), Read(k);
Read(s), Read(t);
for (register int i = ; i <= m; i++) {
Read(x), Read(y), Read(z);
for (register int j = ; j <= k; j++) {
addedge(x + n * j, y + n * j, z);
addedge(y + n * j, x + n * j, z);
if (j < k) {
addedge(x + n * j, y + n * (j + ), );
addedge(y + n * j, x + n * (j + ), );
}
}
}
} Heap heap;
bool vis[maxn]; void Dijsktra()
{
int cn;
memset(dis, inf, sizeof(dis));
dis[s] = ;
heap.insert(s, );
while (heap.node_cn) {
cn = heap.idx[];
heap.pop();
if (vis[cn]) continue;
vis[cn] = true;
for (register int i = fst[cn]; i != -; i = nxt[i]) {
if (!vis[v[i]] && dis[v[i]] > dis[cn] + w[i]) {
dis[v[i]] = dis[cn] + w[i];
heap.insert(v[i], dis[v[i]]);
}
}
}
} void solve()
{
int ans = inf;
Dijsktra();
for (register int i = ; i <= k; i++) ans = min(ans, dis[t + i * n]);
printf("%d\n", ans);
} int main()
{
#ifndef ONLINE_JUDGE
freopen("Motor.in", "r", stdin);
freopen("Motor.out", "w", stdout);
#endif input();
solve(); #ifndef ONLINE_JUDGE
fclose(stdin);
fclose(stdout);
#endif
return ;
}
推荐：堆优化 ， DJ