分层图最短路的AC思路+代码实现；

还是通过模版题来讲解本题为洛谷P4568注意本题是用邻接表堆优化的Dijkstra没学过的可以看我上一条博客讲的就是堆优化的Dijkstra因为本题为无向图而且n,m数据过大建议先看上一条博客这样这道题就很简单好理解了而且可以加深对堆优化的理解注本题为c语言但核心思路一样其他语言的可以复制我的源代码发给AI让AI帮你改语言首先要知道什么是分层图1. 什么是分层图把一张图复制成 k1 层叠起来。第 0 层没用过免费票第 1 层用了 1 张免费票第 2 层用了 2 张免费票...第 k 层用了 k 张免费票每层都是完整的原图。2. 层与层之间怎么连同层之间正常走花钱从上层跳到下层表示用一次免费机会这条边权值为 0比如u (第 x 层) → v (第 x 层)花费 w正常走u (第 x 层) → v (第 x1 层)花费 0免费走3. 为什么要分层因为题目有 /*最多免费 k 条边”这种状态限制 */。我们需要记录到达这个点时用了几张免费票。不同状态不能混在一起.int dis[100001][11]; // 分层最短路 这里dis[u][used] 到u点用了used次免费的最小花费所以dis [u][used] 到达 u 点用了 used 次免费的最小花费这就是分层图最短路。分层图有两种转移1、同层正常走2、跨层免费走上代码#include stdio.h #include stdlib.h #include string.h // 邻接表 int head[100001]; // 每个点的第一条边 int to[100001]; // 边指向的点 int next[100001]; // 下一条边编号 int val[100001]; // 边权 // 分层最短路dis[点][已用免费次数] 最小花费 int dis[100001][11]; int inf 9999999; // 无穷大 int n, m, k, s, t, idx; // 堆节点保存 距离、点、已用免费次数 typedef struct Node { int d; // 当前总花费 int u; // 当前点 int used; // 已用免费次数层数 }Node; Node heap[500001]; // 小根堆 int heapSize; // 堆大小 // 初始化邻接表 void init() { memset(head, -1, sizeof(head)); idx 0; } // 添加一条边 u-v权值w void add(int u, int v, int w) { to[idx] v; val[idx] w; next[idx] head[u]; head[u] idx; } // 堆上浮新节点插入后向上调整 void up(int i) { int flag 0; if (i 1) return; while (i 1 flag 0) { // 比父节点小交换上浮 if (heap[i].d heap[i/2].d) { Node temp heap[i]; heap[i] heap[i/2]; heap[i/2] temp; } else { flag 1; } i / 2; } return; } // 堆下沉堆顶被取出后向下调整 void down(int i) { int t i, flag 0; while (i * 2 heapSize flag 0) { // 找左孩子 if (heap[i].d heap[i*2].d) t i*2; // 找右孩子 if (i*21 heapSize heap[t].d heap[i*21].d) t i*21; if (t ! i) { // 交换并继续下沉 Node temp heap[i]; heap[i] heap[t]; heap[t] temp; i t; } else { flag 1; } } return; } int main() { init(); // 输入城市数、航线数、免费次数、起点、终点 scanf(%d %d %d %d %d, n, m, k, s, t); int a, b, c; for (int i 0; i m; i) { scanf(%d %d %d, a, b, c); add(a, b, c); // 无向图加双向边 add(b, a, c); } // 初始化所有状态为无穷大 for (int i 0; i n; i) { for (int j 0; j k; j) { dis[i][j] inf; } } dis[s][0] 0; // 起点0次免费花费0 // 起点入堆 heapSize; heap[heapSize].d 0; heap[heapSize].u s; heap[heapSize].used 0; up(heapSize); // 堆优化 Dijkstra 核心 while (heapSize 0) { // 取出堆顶当前花费最小的状态 Node now heap[1]; heap[1] heap[heapSize--]; down(1); int d now.d; int u now.u; int used now.used; // 旧数据直接跳过 if (d dis[u][used]) continue; // 遍历所有邻边 for (int i head[u]; i ! -1; i next[i]) { int v to[i]; // 1. 正常走不使用免费层数不变 if (dis[v][used] d val[i]) { dis[v][used] d val[i]; heapSize; heap[heapSize].d dis[v][used]; heap[heapSize].u v; heap[heapSize].used used; up(heapSize); } // 2. 免费走使用一次免费层数1花费不变 if (used k dis[v][used1] d) { dis[v][used1] d; heapSize; heap[heapSize].d dis[v][used1]; heap[heapSize].u v; heap[heapSize].used used 1; up(heapSize); } } } // 答案取到达终点 t用 0~k 次免费的最小值 int ans inf; for (int i 0; i k; i) { if (dis[t][i] ans) ans dis[t][i]; } printf(%d, ans); return 0; }