遇到一个求最短距离的问题，求解答。
《缺氧》是 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 到其他各个水库的最短距离。做这道题的思路是，假设一开始没有道路，只有n个水库。建立一个连通图，初始状态连通图中只有水库 1 一个结点。然后将逐步将道路加入连通图中，道路加入连通图的条件是道路两端的水库至少有一个在连通图中，道路加入连通图后，道路两端的水库都加入连通图。每当有一条道路加入连通图时，计算水库 1 到此道路两端的水库的最短距离是否可以因为这条道路的加入而更短。如果可以，更新水库 1 到这些水库的距离。当所有道路加入连通图后，数组中记录的水库 1 到水库 n 的距离即为所求最短距离。 输入：5 7 [[1,2,3],[1,2,1],[1,5,10],[2,3,4],[2,4,10],[2,5,8],[3,3,9]] 输出：9
2021-12-23 18:37:30赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
