记录编号	261487	评测结果	AAAAAAAAAA
题目名称	[NOIP 2012]文化之旅	最终得分	100
用户昵称	Riolu	是否通过	通过
代码语言	C++	运行时间	0.146 s
提交时间	2016-05-17 19:42:27	内存使用	0.35 MiB

#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
#define N 101
#define INF 99999999
using namespace std;

int n,k,m,s,t;
int cul[N],anti[N][N];
int u,v,w;
int e[N][N];

int main(){
	freopen("culture.in","r",stdin);
	freopen("culture.out","w",stdout);
	
	ios::sync_with_stdio(false);
	int i,j,l;
	memset(e,50,sizeof(e));
	cin>>n>>k>>m>>s>>t;
	for(i=1;i<=n;i++) {cin>>cul[i];e[i][i]=0;}
	for(i=1;i<=k;i++) for(j=1;j<=k;j++) cin>>anti[i][j];
	for(i=1;i<=m;i++) {cin>>u>>v>>w;
		if(e[u][v]>w){e[u][v]=w;e[v][u]=w;}
		if(anti[cul[u]][cul[v]]) e[v][u]=INF;
		if(anti[cul[v]][cul[u]]) e[u][v]=INF;
		}
	for(i=1;i<=n;i++) if(anti[cul[i]][cul[i]]) e[i][i]=INF;
		
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			for(l=1;l<=n;l++)
				if(e[j][i]+e[i][l]<e[j][l]&&(!anti[cul[i]][cul[j]])&&(!anti[cul[l]][cul[i]]))
					e[j][l]=e[j][i]+e[i][l];
	
	if(e[s][t]>=INF) {cout<<-1;}
	else cout<<e[s][t];
	return 0;
	}