本题为标准的分层图板子题，借由此题再次理解一噶分层图。
分层图
啥是分层图哩 就是你建的这个图，他有好几层，神不神奇，腻不腻害！？
分层图是干啥的呢 就是用于处理对边存在额外操作。腻害吧！！
至于具体哩，图请自行搜索dalao博客 各层图之间各自按照原图联通关系连边。
注意只能出上一层到下一层，就像你修了一条道，不可能再修回去。
细节问题 有K次机会时，我们要修K+1层。开数组大小问题：m*(k+1)*4。
对于本题代码如下：
#include<cstdio> #include<queue> #define read(x) scanf("%d",&x)//宏定义，个人习惯 #define INF 0x3f3f3f3f//伪极大值 using namespace std; typedef pair<int, int> pii;//个人习惯 struct Node { int head, dis; }node[210100];//数组大小注意 struct Edge { int to, len, next; }edge[4200100];//数组大小注意 int n, m, k, u, v, w, cnt, ans = INF << 1; void addEdge(int u, int v, int w) { edge[++cnt] = { v,w,node[u].head }; node[u].head = cnt; } //链式前向星存图 void Dijkstra() { for (int i = 1; i <= n * (k + 1); i++) { node[i].dis = INF; } //初始化时，要注意我们的点数已经不是n了，而是n*（k+1） node[1].dis = 0; priority_queue<pii, vector<pii>, greater<pii> >q; //小根堆 q.push({ 0,1 }); while (q.size()) { pii tmp = q.top(); q.pop(); int d = tmp.first, u = tmp.second; if (d != node[u].dis)continue; for (int e = node[u].head; e; e = edge[e].next) { int v = edge[e].to; if (node[v].dis > edge[e].len + d) { node[v].dis = edge[e].len + d; q.push({ node[v].dis,v }); } } } } //最短路板子不解释 int main() { read(n), read(m), read(k); for (int i = 1; i <= m; i++) { read(u), read(v), read(w); for (int j = 0; j <= k; j++) { /* 当j为0时，我们建立的是原图的边 当j不为0时，我们建立的是分身的边 */ addEdge(u + j * n, v + j * n, w); addEdge(v + j * n, u + j * n, w); //上面两行是每层图之间，自身的点的连线，边权不变 if (j == k)break; /* 为什么当j==k时，要退出循环呢？ 因为如果j==k时，还建下面的边，那么就超出范围了 可以自行感性理解一下 */ addEdge(u + j * n, v + (j + 1) * n, 0); addEdge(v + j * n, u + (j + 1) * n, 0); //这两行建立的是层与层之间的边，边权为0 } } Dijkstra(); //跑最短路 for (int i = 0; i <= k; i++) { ans = min(ans, node[n + i * n].dis); //统计每一层到n距离的最小值 } printf("%d ", ans); //输出答案 return 0; }