算法笔试模拟题精解之“最短路”

在线编程介绍

阿里云开发者社区在线编程产品，针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。题库来自笔试模拟题、算法大赛模拟题等，界面整洁明了，操作简单，为用户营造专心答题的学习环境。点击链接开始体验：

https://developer.aliyun.com/coding

本文为大家介绍其中的 第95题：最短路 的题目解析，具体如下：

题目描述

题目等级：容易

知识点：最短路、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)

看完之后是不是有了想法了呢，快来练练手吧>>