开始 2019-06-14 16:00:00

517编程-OI赛制测试赛-普及组

结束 2019-06-14 20:00:00
Contest is over.
当前 2020-05-30 03:51:31

B. 特殊的最短路

描述

有一张n个点的无向图,标号为0到n-1,图中的每条边有两个权值,现在让你求出从0到1的最短路,最短路的定义是W1*W2,W1为路径上第一种权值的和,W2为路径上第二种权值的和,如果没有最短路,输出-1

输入

第一行输入一个整数$n$ ($2 \le n \le 20$)
 

接下来n行每行n个字符,第i行的第j个字符表示weight1[i][j]

再接下来n行每行n个字符,第i行的第j个字符表示weight2[i][j]
 

所有的字符要么是数字要么是'.'
 

第i行的第j个字符是数字表示i,j两个点联通,且权值为这个数字

否则表示不联通

 

输出

输出一个整数

样例

输入

4    	
..14
..94
19..
44..
..94
..14
91..
44..

输出

64

输入

4
..14
..14
11..
44..
..94
..94
99..
44..

输出

36

输入

6    
.....9
..9...
.9.9..
..9.9.
...9.9
9...9.
.....9
..9...
.9.9..
..9.9.
...9.9
9...9.

输出

2025

提示

30分:n <= 5

30分:n <= 10

40分:无限制

时间限制 1 秒
内存限制 128 MB