HDU 1385 Minimum Transport Cost floyd算法输出字典序最小的最短路径

缘起

学习如何使用floyd算法输出最短距离的同时输出”字典序最小的最短路径”. HDU 1385 Minimum Transport Cost

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
P国有N个城市, 任何两个城市之间至多一条道路, 现在货车将从一个城市运输货物到另一个城市.
从一个城市到另一个城市的费用由两部分构成
1. 两个城市之间的距离
2. 经过目的城市的税费（除了目的城市是终点）
你必须写一个程序计算最少费用的路线。

【输入】
第一行是N（N<=1000）, N=0表示输入结束。 每个样例形如
a11 a12 ... a1N
a21 a22 ... a2N
...............
aN1 aN2 ... aNN
b1 b2 ... bN
c d
e f
...
g h
aij是从城市i到城市j的费用, aij=-1表示无路直接从i到j. bi是每个城市的税费.
后面是询问, 表示货车想要从c城市运输货物到d城市. 样例以 g=h=-1结束.

【输出】
From c to d :
Path: c-->c1-->......-->ck-->d
Total cost : ......
......

From e to f :
Path: e-->e1-->..........-->ek-->f
Total cost : ......
注意, 如果方案不止一个, 输出字典序最小的那个. 每个样例之后打印一个空行.

【样例输入】
5
0 3 22 -1 4
3 0 5 -1 -1
22 5 0 9 20
-1 -1 9 0 4
4 -1 20 4 0
5 17 8 3 1
1 3
3 5
2 4
-1 -1
0

【样例输出】
From 1 to 3 :
Path: 1-->5-->4-->3
Total cost : 21

From 3 to 5 :
Path: 3-->4-->5
Total cost : 16

From 2 to 4 :
Path: 2-->1-->5-->4
Total cost : 17

【限制】
1s

因为涉及多个城市之间的最少费用, 所以考虑floyd算法. 但是有以下2个问题要处理

  1. 每个城市有税费. 所以并不是标准的floyd, 如何将问题转换为标准的floyd?
  2. 要求输出字典序最小的路径.

第一个问题处理起来比较简单——就是稍微修改一下floyd算法的板子即可（也就是不能仅仅会套floyd的板子, 还要明白其中的思想.） floyd算法的核心就是

1
g[i][j][k]=min{g[i][j][k-1],g[i][k][k-1]+g[k][j][k-1]} // 借助k与不借助k取min

其中g[i][j][k])表示允许借助顶点1,2,…,k中转产生的从顶点i到顶点j的最短距离

而g[i][j][0] 就是初始的邻接矩阵. 那么因为税费的存在, 所以上述转移方程改为

1
g[i][j][k]=min{g[i][j][k-1],g[i][k][k-1]+g[k][j][k-1]+(k==i||k==j)?0:bk}

其中g[i][j][k]的意义依旧是从i到j借助1,…,k能到达的最少费用. 因为要借助中间城市k, 所以要区分这个中间城市到底是不是真正的中间城市. 但是考虑到真的能使得 g[i][j][k] 变小, 其实k是不会取i或者j的. 所以其实floyd的转移方程改成

1
g[i][j][k]=min{g[i][j][k-1],g[i][k][k-1]+g[k][j][k-1]+bk}

即可. 然后我们来考虑第二个问题. 就是floyd的过程中维护字典序最小的路径. 其实就是如果发现借助中间点k能使得g[i][j] 得到优化的话, 如果真的是严格<的话（即优化后的值真的严格比优化之前小）, 则就不管啥字典序最小了, 如果相等的话, 则就要考虑是否比之前的字典序小. 即令

1
path[i][j]是从i到j的最短路径上的第一个（不是i的）顶点. 所以伊始path[i][j]=j

则打印字典序最小的最短路径时候, 只需要从s（出发点）开始, 每次找到它到达t（目的地）的最短路径上的第一个顶点nxt, 只要它不是t, 就继续找path[nxt][t], 即像下图这般

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
//#include "stdafx.h"
#include <stdio.h>
//#define LOCAL

const int maxn = 1005, inf =0x3f3f3f3f;
int n, g[maxn][maxn], b[maxn], path[maxn][maxn];

void init()
{
	for (int i = 1; i<=n; i++)
	{
		for (int j = 1; j<=n; j++)
		{
			scanf("%d", g[i]+j);
			if (!~g[i][j])
			{
				g[i][j] = inf;
			}
		}
	}
	for (int i = 1; i<=n; i++)
	{
		scanf("%d", b+i);
	}
	for (int i = 1;i<=n; i++)
	{
		for (int j = 1;j<=n; j++)
		{
			path[i][j] = j;
		}
	}
}

void floyd()
{
	for (int k = 1; k<=n; k++)
	{
		for (int i = 1;i<=n; i++)
		{
			for (int j = 1,t; j<=n; j++)
			{
				t = g[i][k]+g[k][j]+b[k];
				if (g[i][j]>t) // 如果真的能优化, 就不管什么字典序了也要优化
				{
					g[i][j] = t;
					path[i][j] = path[i][k];
				}
				else if (g[i][j]==t && path[i][j]>path[i][k]) // 否则就要比较字典序
				{
					path[i][j] = path[i][k];
				}
			}
		}
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	freopen("d:\\my.out", "w", stdout);
#endif
	while(scanf("%d", &n), n)
	{
		init();
		floyd();
		int c,d;
		while(scanf("%d%d", &c, &d), ~c || ~d)
		{
			printf("From %d to %d :\nPath: ",c,d);
			if (c==d)  // 起点和终点可能一样, 艹, WA了一发
			{
				printf("%d\n",c);
			}
			else
			{
				printf("%d-->",c);
				int nxt = path[c][d];
				while(nxt!=d)
				{
					printf("%d-->", nxt);
					nxt = path[nxt][d];
				}
				printf("%d\n", d);
			}
			printf("Total cost : %d\n\n", g[c][d]);
		}
	}
	return 0;
}

ac情况

Status Accepted
Time 15ms
Memory 2004kB
Length 1354
Lang C++
Submitted 2019-10-07 21:55:12
Shared
RemoteRunId 30794683