分数: 400 点
问题陈述
魔法少女Joisino决定将这个世界上存在的每一个数字都变成 1.
重写一个数字 i 与 j (0≤i,j≤9) 成本 c_{i,j} MP(魔法点)。
她现在站在墙前。墙分为 HW 中的方块 H 行和 W 列,并且至少一个方格包含介于 0 和 9 (含)。
你被给予 A_{i,j} 描述了位于 i从顶部数第行和 j左起第列,如下:
- If A_{i,j}≠-1,方块包含一个数字 A_{i,j}.
- If A_{i,j}=-1,方块不包含数字。
求将这面墙上的每个数字变成所需的最少 MP 总量 1 最后。
约束
- 1≤H,W≤200
- 1≤c_{i,j}≤10^3 (i≠j)
- c_{i,j}=0 (i=j)
- -1≤A_{i,j}≤9
- 所有输入值均为整数。
- 墙上至少有一个数字。
输入
输入由标准输入按以下格式给出:
H W
c_{0,0} ... c_{0,9}
:
c_{9,0} ... c_{9,9}
A_{1,1} ... A_{1,W}
:
A_{H,1} ... A_{H,W}
输出
打印将墙上的每个数字变成所需的最小 MP 总量 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
示例输出 1
12
转单 8 进入 1,第一回合是最佳选择 8 进入 4,然后转动 4 进入 9,最后转 9 进入 1,成本核算 6 MP。
墙上包含两个 8s,因此所需的最小总 MP 为 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
示例输出 2
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
示例输出 3
47