PAT 解题报告 1030. Travel Plan (30)

题目描述:

A traveler’s map gives the distances between cities along the highways, together with the cost of each highway. Now you are supposed to write a program to help a traveler to decide the shortest path between his/her starting city and the destination. If such a shortest path is not unique, you are supposed to output the one with the minimum cost, which is guaranteed to be unique.

寻找图上的起点到终点的最短路径并且cost最小的那条最短路径.

算法分析:

最短路径算法的变形题. 就是说现在最短路径可能会有多条, 然后每条边都有权重(cost)和长度(distance), 最短路径定义成distance最短的那条, 当有多条最短路径的时候, 输出cost最少的那条. 所以可以利用Dij算法找到所有的最短路径(记录最短路径的那个parent可能现在要变成list了, 原先是parent[node] = node, 现在是parenet[node] = a list of nodes,考虑可能有多条最短路径), 然后利用dfs, 或者称为回溯, 遍历所有的这写最短路径, 输出cost最小的那条.

Written on August 1, 2013