本文主要是介绍[天梯赛] 图上的动态规划与Dijkstra，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目
刚开始的思路
一开始是想到了要用Dijkstra，但是不知道如何找到多条路径的信息（刚开始是想把所有最短路找到之后再比较找到最大的救援队数量）
正确的思路
在Dijkstra的过程中，分两种情况：
- 找到更短路径进行更新：此时只有一条路可选，并把两个点的信息放入最终路径中，更新路径长
- 找到相同长度的路径：此时要把到达点的路径条数据+=中间点的路径条数，并比较两条路径的救援队数量，更新最终路径。
动态规划思路：从源点出发到点 i 的处理，是最优的，这样一路推到终点，即是最优的。
最终路径信息：最终路径信息采用记录前驱的方法。
参考 ：L2-001-紧急救援*C++(使用Dijkstra算法附带全详细注释） - 神雨临 - 博客园 (cnblogs.com)
这篇关于[天梯赛] 图上的动态规划与Dijkstra的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
