70>算法笔试模拟题精解之“最短路”算法笔试模拟题精解之“最短路”贡献者 | 郭达彬简介：做这道题的思路是，假设一开始没有道路，只有 n 个水库。建立一个连通图，初始状态连通图中只有水库 1 一个结点。然后将逐步将道路加入连通图中，道路加入连通图的条件是道路两端的水库至少有一个在连通图中，道路加入连通图后，道路两端的水库都加入连通图。题目描述题目等级：容易知识点：最短路、DP查看题目：最短路《缺氧》是 Klei Entertainment 所制作并发行的一款模拟游戏。这是一个太空殖民地模拟游戏，玩家需要管理你的复制人，帮助他们挖掘、建立和维护一个地下的小行星基地。你需要水、食物、氧气、适当的调节压力和适宜的温度来维持他们活着并满足他们。在这里，氧气是必不可少的，没有氧气，复制人就会无法生存。电解制氧是一个非常实用的制氧方法，将水通过电解器之后，电解器会消耗水产生氧气和氢气，氧气可以供小人呼吸，氢气则可以进行氢气发电。复制人在进行了一段时间的挖掘之后，在地图里发现了 n 个水库，他们的命名方法非常暴力，水库 1，水库 2，...，水库 n。他们挖掘了 m 条道路将这 n 个水库联通，现在