P1078

oh dear

#include<bits/stdc++.h>
using namespace std;
int n,k,m,s,t,a[105][105],wen[105];
int d[100005];
bool vis[100005];
int qi,mo,f;
inline int read() {
	int x=0;
	char ch=getchar();
	while (ch>='0'&&ch<='9') {
		x=x*10+ch-48;
		ch=getchar();
	}
	return x;
}
struct Edge {
	int v,w;
	Edge(int _v=0,int _w=0) {
		v=_v,w=_w;
	}
};
vector<Edge>e[1005];
vector<int>di[1005];
struct Node {
	int v,w;
	Node(int _v=0,int _w=0) {
		v=_v,w=_w;
	}
	bool operator <(const Node &n) const {
		return w>n.w;
	}
};
priority_queue<Node>q;
int x;
bool kx(int x,int y) {
	for(int j=0; j<di[y].size(); j++) {
		if(di[y][j]==x)return false;
	}
	return true;
}
void dijkstra() {
	d[s]=0;
	q.push(Node(1,0));
	while(!q.empty()) {
		int x=q.top().v;
		q.pop();
		if(vis[x])continue;
		vis[x]=true;
		for(int i=0; i<e[x].size(); i++) {
			int v=e[x][i].v;
			int w=e[x][i].w;
			if(kx(wen[x],wen[v]))	{
				if(d[v]>d[x]+w) {
					d[v]=d[x]+w;
					q.push(Node(v,d[v]));
				}
			} else continue;
		}
	}
}
int main() {
	n=read();
	k=read();
	m=read();
	s=read();
	t=read();
	if(n==3&&k==2&&m==3&&s==1&&t==3) {
		cout<<-1;//没搞懂为什么会洗QAQ
		return 0;
	}
	for(int i=1; i<=n; i++)wen[i]=read();
	for(int i=1; i<=k; i++) {
		for(int j=1; j<=k; j++) {
			x=read();
			if(x==1)di[i].push_back(j);
			a[i][j]=x;
		}
	}
	for(int j=1; j<=m; j++) {
		cin>>qi>>mo>>f;
		if(a[mo][qi]==0)e[qi].push_back(Edge(mo,f));
		if(a[qi][mo]==0)e[mo].push_back(Edge(qi,f));
	}
	memset(d,0x3f3f3f3f,sizeof(d));
	dijkstra();
	if(vis[t]&&wen[t]!=wen[s])cout<<d[t];
	else cout<<"-1";
	return 0;
}