记录编号	346626	评测结果	AAAAAAAAAA
题目名称	[NOIP 2012]文化之旅	最终得分	100
用户昵称	O(1)	是否通过	通过
代码语言	C++	运行时间	0.102 s
提交时间	2016-11-12 11:51:35	内存使用	0.22 MiB

#include<iostream>
#include<cstdio>
using namespace std;

int n,m,k,st,en;

int c[101];
int dx[101][101];
bool fc[101][101];

void work();
void data_cin();

int main()
{
    freopen("culture.in","r",stdin);
	freopen("culture.out","w",stdout);
	data_cin();
	work();
	return 0;
}

void data_cin()
{
	cin>>n>>k>>m>>st>>en;
	for(int i=1;i<=n;i++) cin>>c[i];
	for(int i=1;i<=k;i++)
	{
		for(int j=1;j<=k;j++) cin>>fc[i][j];
	}
	for(int i=1;i<=m;i++)
	{
		int u,v,d;
		cin>>u>>v>>d;
		if(!dx[u][v] || d<dx[u][v]) dx[v][u]=dx[u][v]=d;
	}
}
void work()
{
	if(fc[en][st] || c[st]==c[en])
	{
		cout<<-1;
		return;
	}
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				if(k!=i && k!=j && i!=j)
				{
					if(c[i]!=c[k] && c[i]!=c[j] && c[k]!=c[j])
					{
						if(dx[i][k] && dx[k][j])
						{
							if(!fc[c[k]][c[i]] && !fc[c[j]][c[k]] && !fc[c[j]][c[i]])
							{
								if(!dx[i][j] || dx[i][j]>dx[i][k]+dx[k][j])
									dx[i][j]=dx[j][i]=dx[i][k]+dx[k][j];
							}
						}
					}
				}
			}
		}
	}
	if(!dx[st][en]) cout<<-1;
	else cout<<dx[st][en];
}