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

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#define N 10005
using namespace std;
int n,h,m,s,t,a[105][105],b[105][105],w[105],vis[105];
void hh(int x){for(int i=1;i<=h;i++)if(b[i][h])vis[i]=1;}
int main()
{
	freopen("culture.in","r",stdin);
	freopen("culture.out","w",stdout);
	scanf("%d%d%d%d%d",&n,&h,&m,&s,&t);
	memset(a,40,sizeof(a));
	int x,y,z;
	for(int i=1;i<=n;i++)scanf("%d",&w[i]),a[i][i]=0;
	for(int i=1;i<=h;i++)for(int j=1;j<=h;j++)scanf("%d",&b[i][j]);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		a[x][y]=min(a[x][y],z);
		a[y][x]=a[x][y];
	}	
	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&&k!=i)
					if(!vis[w[i]]&&!vis[w[j]]&&!vis[w[k]])
						if(!b[w[i]][w[k]]&&!b[w[k]][w[j]]&&!b[w[i]][w[j]])
							if(a[i][j]>a[i][k]+a[k][j])
							{
								a[i][j]=a[i][k]+a[k][j];
								hh(w[i]);hh(w[j]);hh(w[k]);
							}
	if(a[s][t]<1000000&&!b[s][t])cout<<a[s][t];
	else cout<<-1;
}