记录编号	449869	评测结果	AAAAAAAAAA
题目名称	[NOIP 2012]文化之旅	最终得分	100
用户昵称	Hyoi_0Koto	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2017-09-15 11:56:02	内存使用	0.00 MiB

#prag\
ma GCC optimize("O3")
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<iostream>
#include<queue>
#define loop(i,j,k) for(int i=j;i<=k;i++)
#define leaf(u) for(int i=head[u];i;i=next[i])
using namespace std;
inline void in(int &x){
    x=0;int f=1;char c=getchar();
    while(!isdigit(c)){if(!(c-'-'))f=-1;c=getchar();}
    while (isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
    x*=f;
}
inline void out(int x){
    if(!x){putchar('0');return;}
    if(x<0)x=~x+1,putchar('-');
    char c[30]={0};
    while(x)c[++c[0]]=x%10+48,x/=10;
    while(c[0])putchar(c[c[0]--]);
}
const int inf=0x7effffff;
const int maxm=10001;
int n,k,m,s,t,u,v,w;
int c[101],a[101][101],ans=inf;
int head[maxm*2],to[maxm*2],val[maxm*2],next[maxm*2],cnt;
inline void add_edge(int u,int v,int w){
	to[++cnt]=v;val[cnt]=w;next[cnt]=head[u];head[u]=cnt;
}
queue<int> q;
int d[101];
bool inq[101];
int gg=1;
inline void spfa(){
	fill(d+1,d+n+1,inf);
	d[s]=0;q.push(s);inq[s]=1;
	while(!q.empty()){
		int u=q.front();q.pop();inq[u]=0;
		leaf(u){
			int v=to[i];
			if(d[v]>d[u]+val[i]){
				d[v]=d[u]+val[i];
				if(!inq[v])q.push(v),inq[v]=1;
			}
		}
	}
}
inline int koto(){
	freopen("culture.in","r",stdin);
    freopen("culture.out","w",stdout);
	in(n);in(k);in(m);in(s);in(t);
	loop(i,1,n) in(c[i]);
	loop(i,1,k)loop(j,1,k) in(a[i][j]);
	loop(i,1,m){
		in(u);in(v);in(w);
		if(!a[c[v]][c[u]])add_edge(u,v,w);
		if(!a[c[u]][c[v]])add_edge(v,u,w);
	}
	spfa();
	if(!(d[t]-inf)) out(-1);else out(d[t]);
}
int hibiki=koto();
int main(){;}