C++ 解法, 执行用时: 4ms, 内存消耗: 472K, 提交时间: 2021-08-11 16:13:47

#include<iostream>
#include<cstring>

using namespace std;
int n;
const int maxn=22;
int f[maxn][maxn][2];

int main(){
	cin>>n;
	memset(f,0x3f3f3f3f,sizeof(f));
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j){
			char c;cin>>c;
			if(c!='.')f[i][j][0]=c-'0';
			if(i==j) f[i][j][0]=0;
		}
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j){
			char c;cin>>c;
			if(c!='.')f[i][j][1]=c-'0';
			if(i==j) f[i][j][1]=0;
		}	 
	for(int k=1;k<=n;++k)
		for(int i=1;i<=n;++i)
			for(int j=1;j<=n;++j){
				f[i][j][0]=min(f[i][k][0]+f[k][j][0],f[i][j][0]);
				f[i][j][1]=min(f[i][k][1]+f[k][j][1],f[i][j][1]);
			}
	if(f[1][2][0]==0x3f3f3f3f || f[1][2][1]==0x3f3f3f3f) cout<<"-1";
	else cout<<f[1][2][0]*f[1][2][1];return 0;
}