#ABC079D. 数字墙
数字墙
题目描述
给定一个 的矩阵。格子中的值为 时,该位置没有数字;否则该位置写有一个 的数字。
另有一张 的费用表 ,其中 表示把数字 改成数字 的费用。每个数字允许连续转换多次,费用相加,不同位置的转换互不影响。
请将所有实际存在的数字都改成 ,并求最少总费用。空位置不需要操作。
输入格式
第一行输入两个整数 。
此后 行,每行输入 个整数,依次给出 $c_{i,0},c_{i,1},\dots,c_{i,9}\left(0\leqq i\leqq9;\ c_{i,i}=0;\ 1\leqq c_{i,j}\leqq10^3\text{ 当 }i\neq j\right)$。费用表的数字编号从 开始。
再输入 行,每行 个整数 $a_{i,1},a_{i,2},\dots,a_{i,m}\left(-1\leqq a_{i,j}\leqq9\right)$,代表墙上的数字。
输出格式
输出一个整数,代表最少总费用。
测试样例
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
样例 1 解释
两个数字 都可以按 转换,每次费用为 。两个数字 无需转换,空格忽略,因此总费用为 。
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 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