P1948 USACO08JAN Telephone Lines S / AcWing 340. 通信线路 - 题解

https://www.luogu.com.cn/problem/P1948
https://www.acwing.com/problem/content/description/342/
方法一 分层图

每次选择从当前点前往另一点时要不要选择付费, 最多选择 \(k\) 次不付费, 所以就是 \(k + 1\) 层图.
具体来说, 假设 \(lev(u, i)\) 为第 \(i\) 层图的 \(u\) 点, 如果对于 \(u\) 如果有一条到 \(v\) 的边, 权值为 \(w\), 那就先在每层 \(lev(u, i) \leftrightarrow lev(v, i)\) 建权值为 \(w\) 的双向边, 再在 \(lev(u, i) \rightarrow lev(v, i + 1)\) 和 \(lev(v, i) \rightarrow lev(u, i +1)\) 建权值为 \(0\) 的单向边, 表示做出了一次不付费的选择, 单向边防止再回来, 确保最多只能做 \(k\) 次不付费选择.
接着跑 \(dijkstra\), \(dist_i\) 表示从 \(1\) 到 \(s\) 的所有路径中权值最大的边权值最小, 然后找出 \(dist_{lev(n, 0, 1, 2 \cdots k)}\) 中最小的那个即可.
[code]#include #include #include #include #include #include using namespace std;#define DLN(x) cout