算法笔试模拟题精解之“最短路”
算法笔试模拟题精解之“最短路”
贡献者 | 郭达彬
简介：做这道题的思路是，假设一开始没有道路，只有 n 个水库。建立一个连通
图，初始状态连通图中只有水库 1 一个结点。然后将逐步将道路加入连通图中，道路
加入连通图的条件是道路两端的水库至少有一个在连通图中，道路加入连通图后，道
路两端的水库都加入连通图。
题目描述
题目等级：容易
知识点：最短路、DP
查看题目：最短路
《缺氧》是 Klei Entertainment 所制作并发行的一款模拟游戏。这是一个太空殖
民地模拟游戏，玩家需要管理你的复制人，帮助他们挖掘、建立和维护一个地下的小
行星基地。你需要水、食物、氧气、适当的调节压力和适宜的温度来维持他们活着并
满足他们。
在这里，氧气是必不可少的，没有氧气，复制人就会无法生存。电解制氧是一个
非常实用的制氧方法，将水通过电解器之后，电解器会消耗水产生氧气和氢气，氧气
可以供小人呼吸，氢气则可以进行氢气发电。
复制人在进行了一段时间的挖掘之后，在地图里发现了 n 个水库，他们的命名
方法非常暴力，水库 1，水库 2，...，水库 n。他们挖掘了 m 条道路将这 n 个水库联
通，现在复制人想知道水库 1 到水库 n 的最短距离。
输入水库数 n、挖掘的道路条数 m (1<= n,m <= 1000) 和一个二维数组 a，其
中 a[i]=x,y,z 表示水库 x 与水库 y 之间的道路长度为 z。
输出水库 1 到水库 n 之间的最短距离。
示例 1
输入：
5
7
[[1,2 ,3],[1 ,2 ,1],[1 ,5 ,10],[2 ,3 ,4],[2, 4, 10],[2, 5 ,8],[3 ,3 ,9]]
输出：
9
解题思路：DP
本题需要用到动态规划算法。
首先可以创建一个数组记录水库 1 到其他各个水库的最短距离。做这道题的思路
是，假设一开始没有道路，只有 n 个水库。建立一个连通图，初始状态连通图中只有
水库 1 一个结点。然后将逐步将道路加入连通图中，道路加入连通图的条件是道路两
端的水库至少有一个在连通图中，道路加入连通图后，道路两端的水库都加入连通图。
每当有一条道路加入连通图时，计算水库 1 到此道路两端的水库的最短距离是否
可以因为这条道路的加入而更短。如果可以，更新水库 1 到这些水库的距离。
当所有道路加入连通图后，数组中记录的水库 1 到水库 n 的距离即为所求最短
距离。
时间复杂度：O(n)
空间复杂度：O(n)
全站分卷索引 · 74 卷
- 1一、算法思想
- 2算法笔试模拟题精解之“打怪兽”
- 31.2 贪心
- 4算法笔试模拟题精解之“最强的团队”
- 5算法笔试模拟题精解之“Tom 爱吃巧克力”
- 6算法笔试模拟题精解之“吃奶酪”
- 7算法笔试模拟题精解之“一的个数”
- 8算法笔试模拟题精解之“Bob 的花束”
- 9算法笔试模拟题精解之“钱庄”
- 10算法笔试模拟题精解之“移动射击”
- 11算法笔试模拟题精解之“相似数组”
- 12算法笔试模拟题精解之“过吊桥”
- 13算法笔试模拟题精解之“完美排列”
- 14算法笔试模拟题精解之“采摘圣诞果”
- 15算法比赛模拟题精解之“Tairitsu and Dynamic Objects”
- 16算法笔试模拟题精解之“Codancer 的炸弹引爆”
- 17算法笔试模拟题精解之“学习小组”
- 18算法笔试模拟题精解之“恢复字符串”
- 191.3 DP/ 动态规划
- 20算法笔试模拟题精解之“寻找等比数列”
- 21算法笔试模拟题精解之“字符配对”
- 22算法笔试模拟题精解之“数组染色”
- 23算法笔试模拟题精解之“连绵的群山”
- 24算法笔试模拟题精解之“难住Tom 的问题”
- 25算法笔试模拟题精解之“变化的字符”
- 26算法笔试模拟题精解之“跳房子”
- 27算法笔试模拟题精解之“寒假活动”
- 28算法笔试模拟题精解之“最短路”
- 29算法笔试模拟题精解之“codancer 上楼”
- 30算法笔试模拟题精解之“木棒拼接”
- 31算法笔试模拟题精解之“Codancer 的数组封印”
- 32算法笔试模拟题精解之“Jerry 的异或运算”
- 33算法笔试模拟题精解之“小明的数学作业”
- 34算法笔试模拟题精解之“奇偶数列”
- 351.4 剪枝
- 361.5 尺取法
- 37算法笔试模拟题精解之“调整数组”
- 38算法笔试模拟题精解之“最优分组”
- 39算法笔试模拟题精解之“破译密码”
- 40二、数据结构
- 412.2 搜索
- 42算法笔试模拟题精解之“能量半径”
- 43算法笔试模拟题精解之“苹果收获程序”
- 44算法笔试模拟题精解之“恐怖的辐射”
- 45算法笔试模拟题精解之“树的拆分”
- 46算法笔试模拟题精解之“Password”
- 47算法笔试模拟题精解之“神奇数字在哪里”
- 48算法笔试模拟题精解之“神奇的棋子”
- 492.3 树
- 50算法笔试模拟题精解之“Codancer 的旅行”
- 51算法笔试模拟题精解之“Codancer 的求和”
- 52算法笔试模拟题精解之“找出二叉搜索树的第2 大的数”
- 532.4 线型
- 54算法笔试模拟题精解之“最活跃的数”
- 55算法笔试模拟题精解之“非递减序列”
- 56算法笔试模拟题精解之“Tom 跳方格”
- 57算法笔试模拟题精解之“复杂的字符串”
- 58算法笔试模拟题精解之“神秘消失”
- 59三、计算
- 60算法笔试模拟题精解之“简单题？
- 61算法笔试模拟题精解之“朋友一生一起走”
- 62算法笔试模拟题精解之“正三角塔”
- 63算法笔试模拟题精解之“组队难题”
- 64算法笔试模拟题精解之“2n 合体”
- 65算法笔试模拟题精解之“平行线”
- 66算法笔试模拟题精解之“叠叠高”
- 67算法笔试模拟题精解之“公平”
- 68算法笔试模拟题精解之“Tom 的手工课”
- 69算法笔试模拟题精解之“填数问题”
- 70算法笔试模拟题精解之“Jerry 的考验”
- 71算法笔试模拟题精解之“超车”
- 72算法笔试模拟题精解之“坏掉的时钟”
- 73算法笔试模拟题精解之“期末考试”
- 74算法笔试模拟题精解之“滑雪比赛”