记录编号	436624	评测结果	AAAAAAAAAA
题目名称	[NOIP 2012]文化之旅	最终得分	100
用户昵称	+1s	是否通过	通过
代码语言	C++	运行时间	0.082 s
提交时间	2017-08-12 09:37:01	内存使用	0.41 MiB

#include<fstream>
using namespace std;
ifstream fin("culture.in");
ofstream fout("culture.out");
int n,k,m,s,t,cul[110],cc[110][110],ma[110][110],act[110];
void vsd(int nat) {
	for(int i=1; i<=n; i++) {
		if(cc[i][cul[nat]]) {
			act[i]=1;
		}
	}
}
int main() {
	fin>>n>>k>>m>>s>>t;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) {
			if(i!=j) {
				ma[i][j]=200000000;
			}
		}
	}
	for(int i=1; i<=n; i++) {
		fin>>cul[i];
	}
	for(int i=1; i<=k; i++) {
		for(int j=1; j<=k; j++) {
			fin>>cc[i][j];
		}
	}
	for(int i=1; i<=m; i++) {
		int u,v,d;
		fin>>u>>v>>d;
		ma[u][v]=d;
		ma[v][u]=d;
	}
	vsd(s);
	for(int k=1; k<=n; k++) {
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=n; j++) {
				if(i!=j&&i!=k&&k!=j) {
					if(!act[i]&&!act[j]&&!act[k]) {
						if(cul[i]!=cul[k]&&cul[k]!=cul[j]) {
							if(!cc[cul[k]][cul[i]]&&!cc[cul[j]][cul[k]]&&!cc[cul[j]][cul[i]]) {
								if(ma[i][k]+ma[k][j]<ma[i][j]) {
									ma[i][j]=ma[i][k]+ma[k][j];
									vsd(i);
									vsd(k);
									vsd(j);
								}
							}
						}
					}
				}
			}
		}
	}
	if(ma[s][t]!=200000000&&!act[t])
		fout<<ma[s][t]<<endl;
	else
		fout<<-1<<endl;
	return 0;
}