#ABC079D. 数字墙

数字墙

题目描述

\hspace{15pt}给定一个 n×mn\times m 的矩阵。格子中的值为 −1-1 时,该位置没有数字;否则该位置写有一个 0∼90\sim9 的数字。

\hspace{15pt}另有一张 10×1010\times10 的费用表 cc,其中 ci,jc_{i,j} 表示把数字 ii 改成数字 jj 的费用。每个数字允许连续转换多次,费用相加,不同位置的转换互不影响。

\hspace{15pt}请将所有实际存在的数字都改成 11,并求最少总费用。空位置不需要操作。

输入格式

\hspace{15pt}第一行输入两个整数 n,m(1≦n,m≦200)n,m\left(1\leqq n,m\leqq200\right)。

\hspace{15pt}此后 1010 行,每行输入 1010 个整数,依次给出 $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)$。费用表的数字编号从 00 开始。

\hspace{15pt}再输入 nn 行,每行 mm 个整数 $a_{i,1},a_{i,2},\dots,a_{i,m}\left(-1\leqq a_{i,j}\leqq9\right)$,代表墙上的数字。

输出格式

\hspace{15pt}输出一个整数,代表最少总费用。

测试样例

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 解释

\hspace{15pt}两个数字 88 都可以按 8→4→9→18\to4\to9\to1 转换,每次费用为 2+2+2=62+2+2=6。两个数字 11 无需转换,空格忽略,因此总费用为 1212。

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