记录编号	202241	评测结果	AAAAAAAAAA
题目名称	[NOIP 2012]文化之旅	最终得分	100
用户昵称	forever	是否通过	通过
代码语言	C++	运行时间	0.038 s
提交时间	2015-10-31 21:09:08	内存使用	0.37 MiB

#include<cstdio>
#include<cstring>
using namespace std;
int n,m,s,t,K;
int culture[102],dis[102][102];
int a[102][102];
int main(){
    freopen("culture.in","r",stdin);
	freopen("culture.out","w",stdout);
	scanf("%d%d%d%d%d",&n,&K,&m,&s,&t);
	for(int i=1;i<=n;++i) scanf("%d",&culture[i]);
	for(int i=1;i<=K;++i) for(int j=1;j<=K;++j) scanf("%d",&a[i][j]);
	int u,v,d;
	memset(dis,25,sizeof(dis));
	for(int i=1;i<=m;++i) {
		scanf("%d%d%d",&u,&v,&d);
		if(!a[u][v]&&dis[v][u]>d) dis[v][u]=d;
		if(!a[v][u]&&dis[u][v]>d) dis[u][v]=d;
	  }
	for(int k=1;k<=n;++k){
		for(int i=1;i<=n;++i){
			for(int j=1;j<=n;++j){
				if(i!=j&&j!=k&&i!=k&&!a[culture[k]][culture[i]]&&!a[culture[j]][culture[i]]&&!a[culture[j]][culture[k]]&&culture[i]!=culture[j]&&culture[j]!=culture[k]&&culture[k]!=culture[i]){
					if(dis[i][j]>dis[i][k]+dis[k][j]) dis[i][j]=dis[i][k]+dis[k][j];
				}
			}
		}
	}
	if(dis[s][t]>1000000) puts("-1");
	else printf("%d",dis[s][t]);
	getchar();getchar();
	return 0;
}