shortest-path.md

最短路

全部标签

数据结构

数组 矩阵 链表 双向链表 栈 单调栈 队列 单调队列 堆（优先队列） 哈希表 字符串 字符串匹配 树 二叉树 二叉搜索树 最小生成树 图 有序集合 拓扑排序 最短路 强连通分量 欧拉回路 双连通分量 并查集 字典树 线段树 树状数组 后缀数组

算法

枚举 递归 分治 回溯 贪心 动态规划 排序 桶排序 计数排序 基数排序 归并排序 快速选择 二分查找 记忆化搜索 深度优先搜索 广度优先搜索 双指针 位运算 前缀和 计数 滑动窗口 状态压缩 哈希函数 滚动哈希 扫描线

其他

数学 数论 几何 博弈 模拟 组合数学 随机化 概率与统计 水塘抽样 拒绝采样 数据库 设计 数据流 脑筋急转弯 交互 迭代器 多线程

---

题号	标题	题解	标签	难度
399	除法求值	[✓]	深度优先搜索 广度优先搜索 并查集 4+	Medium
499	迷宫 III 🔒		深度优先搜索 广度优先搜索 图 5+	Hard
505	迷宫 II 🔒		深度优先搜索 广度优先搜索 图 4+	Medium
743	网络延迟时间		深度优先搜索 广度优先搜索 图 2+	Medium
787	K 站中转内最便宜的航班		深度优先搜索 广度优先搜索 图 3+	Medium
882	细分图中的可到达节点		图 最短路 堆（优先队列）	Hard
1334	阈值距离内邻居最少的城市		图 动态规划 最短路	Medium
1368	使网格图至少有一条有效路径的最小代价		广度优先搜索 图 数组 3+	Hard
1514	概率最大的路径		图 数组 最短路 1+	Medium
1786	从第一个节点出发到最后一个节点的受限路径数		图 拓扑排序 动态规划 2+	Medium
1976	到达目的地的方案数		图 拓扑排序 动态规划 1+	Medium
2045	到达目的地的第二短时间		广度优先搜索 图 最短路	Hard
2093	前往目标城市的最小费用 🔒		图 最短路 堆（优先队列）	Medium
2203	得到要求路径的最小带权子图		图 最短路	Hard
2290	到达角落需要移除障碍物的最小数目		广度优先搜索 图 数组 3+	Hard
2297	跳跃游戏 VIII 🔒		栈 图 数组 3+	Medium
2473	购买苹果的最低成本 🔒		图 数组 最短路 1+	Medium
2577	在网格图中访问一个格子的最少时间		广度优先搜索 图 数组 3+	Hard
2642	设计可以求最短路径的图类		图 设计 最短路 1+	Hard
2662	前往目标的最小代价		图 数组 最短路 1+	Medium
2699	修改图中的边权		图 最短路 堆（优先队列）	Hard
2714	找到 K 次跨越的最短路径 🔒		图 最短路 堆（优先队列）	Hard
2737	找到最近的标记节点 🔒		图 数组 最短路 1+	Medium
2959	关闭分部的可行集合数目		位运算 图 枚举 2+	Hard
2976	转换字符串的最小成本 I		图 数组 字符串 1+	Medium
2977	转换字符串的最小成本 II		图 字典树 数组 3+	Hard
3112	访问消失节点的最少时间		图 数组 最短路 1+	Medium
3123	最短路径中的边		深度优先搜索 广度优先搜索 图 2+	Hard
3286	穿越网格图的安全路径		广度优先搜索 图 数组 3+	Medium
LCP 35	电动车游城市		图 最短路 堆（优先队列）	Hard
LCP 56	信物传送		广度优先搜索 图 数组 3+	Medium
剑指 Offer II 111	计算除法	[✓]	深度优先搜索 广度优先搜索 并查集 3+	Medium