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

#define inf 0x2fffffff
#define Min(a,b)((a)<(b)?(a):(b))

#include<map>
#include<queue>
#include<cstdio>
#include<bitset>
#include<iostream>

using namespace std;

struct My_define{
	bitset<150>sta;
	friend bool operator < (My_define a,My_define b){
		return a.sta[0]<b.sta[0];
	}
}My,_My;

int tot,c[150];
bitset<150>Link[150];
int n,k,m,s,t,first[200],Ans;
map<pair<int,My_define>,int>dis;
map<pair<int,My_define>,bool>vis;

struct Edge{
	int u,v,w,next;
}edge[50010];

struct Que{
	int ver,w;
	bitset<150>sta;
}temp,p;

void Add(int u,int v,int w)
{
	edge[++tot].u=u;
	edge[tot].v=v;
	edge[tot].w=w;
	edge[tot].next=first[u];
	first[u]=tot;
}

int spfa()
{
	queue<Que>q;temp.ver=s;Ans=inf;
	temp.sta[c[s]]=1;temp.w=0;q.push(temp);
	My.sta=temp.sta;
	dis[make_pair(s,My)]=0;
	while(!q.empty()){
		p=q.front();q.pop();My.sta=p.sta;
		vis[make_pair(p.ver,My)]=false;
		if(p.ver==t)Ans=Min(Ans,dis[make_pair(p.ver,My)]);
		for(int i=first[p.ver];i;i=edge[i].next){
			bitset<150>temp_s=p.sta&Link[c[edge[i].v]];
			if(temp_s.count()>0)continue;
			temp.sta=p.sta;temp.sta[c[edge[i].v]]=1;
			My.sta=temp.sta;_My.sta=p.sta;
			if((!dis.count(make_pair(edge[i].v,My)))){
                dis[make_pair(edge[i].v,My)]=dis[make_pair(p.ver,_My)]+edge[i].w;
                temp.ver=edge[i].v;q.push(temp);vis[make_pair(edge[i].v,My)]=true;
			}
			else
			  	if(dis[make_pair(edge[i].v,My)]>dis[make_pair(p.ver,_My)]+edge[i].w){
              		dis[make_pair(edge[i].v,My)]=dis[make_pair(p.ver,_My)]+edge[i].w;
              		if(!vis[make_pair(edge[i].v,My)]){
						temp.ver=edge[i].v,q.push(temp);
						vis[make_pair(edge[i].v,My)]=1;
              		}
			  	}
		}
	}
	if(Ans>=inf)return -1;
	else return Ans;
}

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",&c[i]);
	for(int i=1,tmp;i<=k;i++)for(int j=1;j<=k;j++){
		scanf("%d",&tmp);
		if(tmp==0)Link[i][j]=0;
		else Link[i][j]=1;
	}
	for(int i=1,u,v,w;i<=m;i++)
		scanf("%d%d%d",&u,&v,&w),Add(u,v,w),Add(v,u,w);
	printf("%d",spfa());
}