有关「最短路径问题」的一些习题及思考

Feb. 17th, 2016


算法 最短路径问题 习题

看了最短路径问题的相关算法和思想之后找了一些题目练习一下,这里记录一下思路和代码,方便查看。

POJ-3615
题意:牛要进行跳栏杆比赛,栏杆高度不同,牛只关心最高的栏杆,给出中间站的个数和某些站之间的一条单向路径(one-way path)及栏杆高度。最后给出若干个起点终点的数据,要求输出最高栏杆的最低可能高度
思路:起点和终点都不定,考虑用Floyd算法,将栏杆的高度作为路径的权重,求所有路径中最大边权的最小可能权重。根据复杂度($300^3\approx10^7$),只要稍微修改算法循环体内的条件即可
View Code in Github Repository

POJ-1125
题意:股票经纪人互相之间要传递消息,而且每个人都只会从他相信的人那里获取信息,而获取信息需要付出一定时间代价,求第一个发散消息的人及让所有人都获取到信息的最小时间代价。给出人之间的相互信任关系和消息传播的时间代价
思路:因为起点不确定,将信息传递方向和时间代价看成单向边及权重。用Floyd算法算全源最短路径,为毛题目里没给数据范围...
View Code in Github Repository

POJ-3259
题意:连通农场之间的路径有两种,一种是正时间权重的路径,一种是负时间权重的“虫洞”(即在出发前的时间到达终点),给出若干条路径及权重,求是否可以在出发时间之前从某个起点到达某个终点
思路:即判断在所有边构成的有向图中是否存在负权回路,由于所有的农场都可达,将任一农场作为源点即可,用Bellman-Ford算法判断是否有负权回路即可,复杂度为$5\times500\times2700\approx10^7$
View Code in Github Repository

POJ-1847
题意:电车网络包含了一系列交点和线路,电车到达交点处只能从开关指向的方向离开,否则要调整开关指向,给出若干条可达线路及开关的初始指向,求从起点到终点的最小调整开关次数
思路:将开关初始指向的线路权重设为0,其余线路权重设为1,求从源点出发到达终点的路径的最小权重即可,用Dijkstra算法求单源最短路径即可,直接用邻接矩阵来表示,复杂度为$100^2=10^4$
View Code in Github Repository

POJ-3268
题意:牛去参加聚会,指定到第i号牛家里,给出若干条从A号牛家到B号牛家的路及时间,注意是单向边,来与去的权重不同,求除了第i只牛外,哪一只牛从去参加聚会到回到家里花费的时间最少
思路:将时间看作权重,注意到第i只牛的家一次为起点一次为终点,作为起点时(即牛各回各家),求以i为源点的单源最短路径即可;作为终点时,不能仅仅是将p[i][j]化为p[j][i],还有矩阵转置神马的...考虑另一种方案,即将所有的边反向,求第i头牛到其他牛家的最短路径即可,最后将两个路径加起来取最小值。用Dijkstra算法,复杂度为$2\times1000^2\approx10^6$
View Code in Github Repository

POJ-1797
题意:城市里有若干条双向路,每条路上有限重,从编号为1的源点开始,求到达其他点的路径能承载的最大重量(能承载的重量取决于限重最大的一条路)
思路:在遍历从源点到终点的所有路径中,总是选取当前限重最大的路径(最优子结构性质),最后将最大限重输出即可,使用Dijkstra算法,将更改路径限重的循环修改即可,复杂度为$1000^2=10^6$
View Code in Github Repository

POJ-2253
题意:青蛙跳石头,给出若干个石头的坐标,目的是从1号石头跳到2号石头,在这个过程中令每一次跳跃距离都尽可能小,求这些跳跃距离中最大的一个
思路:在遍历每次要跳跃的顶点时都选择当前距离最小的顶点进行跳跃,将该顶点加入到已确定顶点集合中,修正其他顶点到集合里顶点的最短距离,与最短路的区别在于,如果出现一条比当前已确定顶点集合中顶点间路径更小的距离,则要重新建立集合,进行修正。仍然是用Dijkstra算法,复杂度为$200^2\approx10^5$
View Code in Github Repository

POJ-2387
题意:给出若干条带权双向路径,一个人从编号为N的地方走到编号为1的地方,求最短路径长度
思路:直接套用Dijkstra算法模板即可,复杂度为$1000^2=10^6$
View Code in Github Repository

南阳理工OJ-115
题意:有n个部队和m个城市,给出可达城市之间的耗时,部队驻扎在一些城市中,求部队到达指定城市需要的最短时间
思路:将指定的城市看作源点,耗时作为权重,求该点到达n个部队驻扎城市的最短距离,用Dijkstra算法,复杂度为$1000^2=10^6$

HDOJ-1217
题意:给出一系列的货币换算率,求有没有可能在经过一系列交换货币之后交换回原来的货币时拿到比原来更多的钱
思路:由于源货币不确定,考虑用Floyd算法求“最长路径”,即换算之前c[i][i]=1,换算之后变成了c[i][i]>1.更改循环体条件即可。感觉主要是如何用map将输入的字符串转换为整型数据表。复杂度为$30^3\approx10^5$
View Code in Github Repository

HDOJ-1224
题意:给出一系列城市的有趣指数,在从起点出发最终回到起点的过程中不会两次经过同一个城市(除起点外),求一条兴趣指数最大的旅游路线
思路:将有趣指数看作权重,求一条最长路径,即修改$v>u+cost$为$v < u+cost$即可,关键是题目要求构造出一个最优解,意味着在计算最长路的过程中要保存前驱节点的信息,方便最后进行还原。这里用了SPFA算法 来提高效率(好吧并不需要提高...)
View Code in Github Repository