图的最短路径有关问题
图的最短路径问题
迪杰特斯拉可以解决单权的最短路径,如果有两个权的时候,在第一个权相等的时候比较第二权,该用什么算法
Description
给你n个点,m条无向边,每条边都有长度d和花费p,给你起点s终点t,要求输出起点到终点的最短距离及其花费,如果最短距离有多条路线,则输出花费最少的。
Input
输入n,m,点的编号是1~n,然后是m行,每行4个数 a,b,d,p,表示a和b之间有一条边,且其长度为d,花费为p。最后一行是两个数 s,t;起点s,终点。n和m为0时输入结束。
Output
输出 一行有两个数, 最短距离及其花费。
Sample Input
3 2
1 2 5 6
2 3 4 5
1 3
0 0
Sample Output
9 11
------解决方案--------------------
最简单地做法:将两个权值结合起来,构成一个单权。
比如第一个权值范围在2000以内,第二个在5000以内。于是我们把第一个权值乘上5000,然后和第二个权值相加,用和做权值进行计算。
第一权值的差异有决定性作用,而当它无差异时则第二权值发生作用。解决了。
迪杰特斯拉可以解决单权的最短路径,如果有两个权的时候,在第一个权相等的时候比较第二权,该用什么算法
Description
给你n个点,m条无向边,每条边都有长度d和花费p,给你起点s终点t,要求输出起点到终点的最短距离及其花费,如果最短距离有多条路线,则输出花费最少的。
Input
输入n,m,点的编号是1~n,然后是m行,每行4个数 a,b,d,p,表示a和b之间有一条边,且其长度为d,花费为p。最后一行是两个数 s,t;起点s,终点。n和m为0时输入结束。
Output
输出 一行有两个数, 最短距离及其花费。
Sample Input
3 2
1 2 5 6
2 3 4 5
1 3
0 0
Sample Output
9 11
------解决方案--------------------
最简单地做法:将两个权值结合起来,构成一个单权。
比如第一个权值范围在2000以内,第二个在5000以内。于是我们把第一个权值乘上5000,然后和第二个权值相加,用和做权值进行计算。
第一权值的差异有决定性作用,而当它无差异时则第二权值发生作用。解决了。