PAT 解题报告 1003. Emergency (25)

题目描述:

抽象出来就是给你一张图,给你起点终点,着到起点到终点的所有最短路径,每个点上有一个数,代表这个点上的搜救队的数量,要求输出这些最短路径中你能召集到的最大的搜救队的数量。

算法分析:

简单题,最短路径算法(e.g. Dijastra),但是要稍微变化一下,要记录所有的的最短路径,所以从终点回溯上去可能有多于一个的parent。那么就在每个node上面挂一个list好了,记录所有的parents. 得到后可以从终点DFS到起点,记录下每条最短路径上的搜救队的数量和。保存最大的那个输出即可。

注意点:

这个题目其实就是最短路径的小小变形,注意最原始的最短路径算法通过记录每个node最短路径上的parent来保存一条这样的最短路径,这里话就是相当于,要多点判断,当新的路径和当前路径相同长度时,也要记录下来,但是后面如果找到更短的,那么之前的路径就要清空,记录路径的代码稍微注意一点就没问题了。

Written on January 18, 2013