题解 P4568 【[JLOI2011]飞行路线】

**分层图最短路**板子题。 对于图中的每个结点 $u$，可以把它拆成 $k + 1$ 个节点 $u_j, j \in [0, k]$，分别表示当使用 $j$ 次免费通行权限后到达 $u$ 号节点的状态。对于样例，则可以这样表示（图画得不是很好，见谅）：  图中加粗结点表示样例的起点和终点。 事实上，虽然样例可以用这种方法画图表示，但我们写代码的时候不一定要建这么多结点。只需要按照原始的输入建普通的图。考虑 dp。设 $\text{dis}_{i, j}$ 表示当前从起点 $i$ 号结点，使用了 $j$ 次免费通行权限后的最短路径。显然，$\text{dis}$ 数组可以这么转移： $$ \text{dis}_{i, j} = \min\{\min\{\text{dis}_{from, j - 1}\}, \min\{\text{dis}_{from,j} + w\}\} $$ 其中，$from$ 表示 $i$ 的父亲节点，$w$ 表示当前所走的边的边权。当 $j - 1 \geq k$ 时，$\text{dis}_{from, j}$ = $\infty$。 事实上，这个 dp 就相当于对于每个结点的 $k + 1$ 个状态，想象成拆为 $k + 1$ 个不同的结点，每个结点之间可以相连，仿佛这张图一共有 $k + 1$ 层。 对于进行 Dijkstra 算法的过程，把 $\text{done}$ 数组也开成二维就好，每次入队的时候分别判断能否使用免费通行权限即可。最后统计答案的时候需要统计出到最后一个结点总共 $k + 1$ 种状态的最短距离。 核心代码如下： ```cpp struct State { // 优先队列的结点结构体 int v, w, cnt; // cnt 表示已经使用多少次免费通行权限 State() {} State(int v, int w, int cnt) : v(v), w(w), cnt(cnt) {} bool operator<(const State &rhs) const { return w > rhs.w; } }; void dijkstra() { memset(dis, 0x3f, sizeof dis); dis[s][0] = 0; pq.push(State(s, 0, 0)); // 到起点不需要使用免费通行权，距离为零 while (!pq.empty()) { const State top = pq.top(); pq.pop(); int u = top.v, nowCnt = top.cnt; if (done[u][nowCnt]) continue; done[u][nowCnt] = true; for (int i = head[u]; i; i = edge[i].next) { int v = edge[i].v, w = edge[i].w; if (nowCnt < k && dis[v][nowCnt + 1] > dis[u][nowCnt]) { // 可以免费通行 dis[v][nowCnt + 1] = dis[u][nowCnt]; pq.push(State(v, dis[v][nowCnt + 1], nowCnt + 1)); } if (dis[v][nowCnt] > dis[u][nowCnt] + w) { // 不可以免费通行 dis[v][nowCnt] = dis[u][nowCnt] + w; pq.push(State(v, dis[v][nowCnt], nowCnt)); } } } } int main() { n = read(), m = read(), k = read(); // 笔者习惯从 1 到 n 编号，而这道题是从 0 到 n - 1，所以要处理一下 s = read() + 1, t = read() + 1; while (m--) { int u = read() + 1, v = read() + 1, w = read(); add(u, v, w), add(v, u, w); // 这道题是双向边 } dijkstra(); int ans = std::numeric_limits<int>::max(); // ans 取 int 最大值为初值 for (int i = 0; i <= k; ++i) ans = std::min(ans, dis[t][i]); // 对到达终点的所有情况取最优值 println(ans); } ```