标签：短路 算法 dijkstra mathcal maze 10.16 CW dp 关键点

题面

传统 T4 找不到原题
挂个 pdf
题面下载

算法

不容易想到把出发点, 有被困同伴的人称作关键点
那么只需要求出关键点之间, 关键点到任意一个终点的最短距离, 然后在搜索即可求解

dijkstra 算法求单源最短路

\(n > 10^3\), 显然会 T 飞

dijkstra 算法求单源最短路

\(\mathcal{O}(k m \log m + k!)\)
只能通过 \(50\%\) 的点

状态压缩 dp + 堆优化 dijkstra

观察到 \(k\) 很小, 考虑优化搜索

状态定义

用 \(f_{i, S}\), 表示当前在 \(i\) 点, 经过的关键点集合为 \(S\) 时, 最短路径

边界条件与初始化

\[f_{i, 1 \mathcal{<<} i} = dis_{i, s} \]

状态转移方程

\[f_{i, \mathcal{S}} = \min^{j = 1}_{k} (f_{j, \mathcal{S} - (1 \mathcal{<<} i)} + dis_{i, j} \times SIZE_\mathcal{S}) \]

时间复杂度

代码

后补

总结

对于一些有多个阶段(本题中为解救同伴)这一类型的题目

• 分层图
• 全源最短路
• dp

本题中将每一个特殊点抽象出来的思路值得学习
搜索效率不高时考虑转化 dp

标签：短路,算法,dijkstra,mathcal,maze,10.16,CW,dp,关键点
From： https://www.cnblogs.com/YzaCsp/p/18471291