乐趣区

AtCoder-Context-ABC-079-D-Wall

jiezi

本文章为原创文章，未经过允许不得转载
运行要求
运行时间限制: 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 算法求最短路径

步骤

  1. 遍历每一个点，把这个点看作中转站 A。
  2. 在 1 的基础上遍历所有的点。所有的点，包括这个点自己，比如点 X，经过这个中转站 A，到达目标点 B 的距离设为 distanceXAB
  3. 点 X 到目标点 B 的目前最短距离为 XB(注意，这里可能已经不是直接距离了)
  4. 对比，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)

总结

※ 另外，我会在我的微信个人订阅号上推出一些文章，欢迎关注

退出移动版