共计 2493 个字符，预计需要花费 7 分钟才能阅读完成。
本文章为原创文章，未经过允许不得转载
运行要求
运行时间限制: 2sec
内存限制: 1024MB
未经允许，不得许转载
原题链接
题目
魔法少女想要把这个世界上所有的数字都变为 1
把一个数字从 i 变成 j 需要 cij 个魔法点数。0<=i,j<=9
现在面前有一堵墙，宽为 W，高为 H。只要有一个砖块里写着 0 以上 9 以下的整数。
从上往下，从左往右 i 行（1<=i<=H）, 第 j 列(1<=j<=W), 写着数情报 Aij
- Aij = -1 的情况下，代表砖头上没有写数字
- Aij！= -1 的情况下，代表砖头上写着数字 Aij
求把墙壁上所有的数字都变成 1，所需要的最小魔法值。
输入前提条件
- 所有的输入均为整数
- 1 <= H,W <= 200
- cij = 0 (i = j)
- -1 <= Aij <= 9
- 墙上至少写了一个整数
输入
输入按照以下形式标准输入
H W
c0,0 ... c0,9
::
c9,0 ... c9,9
A1,1 ... A1,W
:
AH,1 ... AH,W输出
输出把墙壁上所有的数都变成 1，所需要的最小魔法值
例 1
输入
2 4
0 9 9 9 9 9 9 9 9 9
9 0 9 9 9 9 9 9 9 9
9 9 0 9 9 9 9 9 9 9
9 9 9 0 9 9 9 9 9 9
9 9 9 9 0 9 9 9 9 2
9 9 9 9 9 0 9 9 9 9
9 9 9 9 9 9 0 9 9 9
9 9 9 9 9 9 9 0 9 9
9 9 9 9 2 9 9 9 0 9
9 2 9 9 9 9 9 9 9 0
-1 -1 -1 -1
8 1 1 8输出
12要把 8 变成 1 的话，先把 8 变成 4，再把 4 变成 9
墙壁上有 2 个 8，所以总共需要 6 *2=12 点魔法值
例 2
输入
5 5
0 999 999 999 999 999 999 999 999 999
999 0 999 999 999 999 999 999 999 999
999 999 0 999 999 999 999 999 999 999
999 999 999 0 999 999 999 999 999 999
999 999 999 999 0 999 999 999 999 999
999 999 999 999 999 0 999 999 999 999
999 999 999 999 999 999 0 999 999 999
999 999 999 999 999 999 999 0 999 999
999 999 999 999 999 999 999 999 0 999
999 999 999 999 999 999 999 999 999 0
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1输出
0请注意，墙壁上的数不需要改变的情况
例 3
输入
3 5
0 4 3 6 2 7 2 5 3 3
4 0 5 3 7 5 3 7 2 7
5 7 0 7 2 9 3 2 9 1
3 6 2 0 2 4 6 4 2 3
3 5 7 4 0 6 9 7 6 7
9 8 5 2 2 0 4 7 6 5
5 4 6 3 2 3 0 5 4 3
3 6 2 3 4 2 4 0 8 9
4 6 5 4 3 5 3 2 0 8
2 1 3 4 5 7 8 6 4 0
3 5 2 6 1
2 5 3 2 1
6 9 2 5 6输出
47读懂题目
墙上写的 cij 的情报，代表了两个点之间的相互距离
如图所示，打个比方。有 4 个点。左边是墙上的情报。墙上的情报代表点和点之间的相互距离。右边的图，描绘了点和点之间的距离。
解题思路
我们已知点和点之间的直接距离。每个点到 1 的距离的和就是把所有的点变成 1 所需要的魔法值
但是，每个点到 1 的路线，除了直接线路以外，还有间接线路
比如上图中，1 到 4 的直接距离是 180
但是 1 到 4 的间接路线还有 1 ->2->4
总共消耗 65 点魔法值
因此可以看出，每个点到 1 的路线虽然有直接路线，但是因为其他路线也通。所以，对于每一个点，我们要找到这个点到 1 的最短路径。
直接了断来说，floyd 算法求最短路径
步骤
- 遍历每一个点，把这个点看作中转站 A。
- 在 1 的基础上遍历所有的点。所有的点，包括这个点自己，比如点 X，经过这个中转站 A，到达目标点 B 的距离设为 distanceXAB
- 点 X 到目标点 B 的目前最短距离为 XB(注意，这里可能已经不是直接距离了)
- 对比，distanceXAB 和 distanceXB，如果 distanceXAB 比 distanceXB 要小，那么用 distanceXB 去覆盖 distanceXAB。覆盖的不光是距离，还有路线
以 1 为中转站
如上图，刚开始的时候，1 为中转站，我们发现经过 1 到达别的地方，和直接到达别的地方相比，要么距离一样，要么还要远
3->1->4 distance = 20+180 = 200
3->4 distance = 5
1->1 distance = 0
1->1->1 distance = 0
我们不更新路径
以 2 为中转站
这种情况下
1->4 distance = 180
1->2->4 distance = 65
1 经过 2 到 4
比
目前的 1 直接到 4
的路径距离要近
我们用 1 ->2->4 的路线去覆盖 1 ->4 的路线
用 65 去覆盖 180
类似的情况还有 1 到 3，3 到 1，4 到 1
以 3 为中转站
同理，当遍历到 3，以 3 为中转站的时候
比如 1 - 4 的走法，已经被更新为 1 ->2->4 distnace 65
但是如果经过 3 的话，1->2->3->4 distance 16
显然经过 3 到 4 会更近
1 到 4，2 到 4
4 到 1，4 到 2
会在原来的基础上选择经过 3 来到达目的地，这样会更近一些
以 4 为中转站
我们发现在已有的路线下，好多都已经不是原本的直达，就算经过 4 也没能缩短路径距离，所以没有线路被更新
就这样遍历每个点，把每个点当作中转站，然后判断是不是要经过这个中转站
总结
floyd 算法求最短路径的精髓就在于，每次短路线覆盖长路线，覆盖的不仅仅是距离本身，实际上还隐藏覆盖了路线
代码
H, W = map(int,input().split())
ARR = []
for i in range(10):
res = list(map(int, input().split()))
ARR.append(res)
CRR = []
for i in range(H):
CRR.append(list(map(int, input().split())))
def calculate(h, w, arr, crr):
for i in range(0, 10):
for j in range(0, 10):
for k in range(0, 10):
s1 = arr[j][i] + arr[i][k]
s2 = arr[j][k]
arr[j][k] = min(s1, s2)
result = 0
for cr in crr:
for c in cr:
if c == -1:
continue
else:
result += arr[1]
print(result)
calculate(H, W, ARR, CRR)
总结
※ 另外，我会在我的微信个人订阅号上推出一些文章，欢迎关注
