【题解】文化之旅

#include<bits/stdc++.h> 
using namespace std;
int n,k,m,s,t,c[109],a[109][109],dis[109];
bool vis[109];
bool vc[109];
vector<pair<int,int>> ve[109];
bool good(int u,int v){
	int i=c[u];
	int j=c[v];
	if(vc[j]==1) return false;
	if(c[u]==c[v]) return false;
	for(int i=1;i<=n;i++){
		if(vc[c[i]]==1){
			if(a[c[v]][c[i]]==1)
				return false;
			if(c[v]==c[i])
				return false;
		}
	}
	return true;
}
void dijkstra(int s){
	memset(dis,0x3f,sizeof(dis));
	priority_queue<pair<int,int>> que;
	dis[s]=0;
	que.push({0,s});
	while(!que.empty()){
		int u=que.top().second;
		int v=que.top().first;
		que.pop();
		if(vis[u]==1) continue;
		vis[u]=1;
		vc[c[u]]=1;
		if(good(u,v)){
			for(auto vv:ve[u]){
				int v=vv.first;
				int w=vv.second;
				if(dis[v]>dis[u]+w){
					dis[v]=dis[u]+w;
					if(vis[v]==0){
						que.push({-dis[v],v});
					}
				}
			}
		}
		
	}
}
int main(){
	cin>>n>>k>>m>>s>>t;
	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>>a[i][j];
		}
	}
	for(int k=1;k<=m;k++){
		int u,v,d;
		cin>>u>>v>>d;
		int i=c[u];
		int j=c[v];
		if(a[j][i]==0)
			ve[u].push_back({v,d}); 
		if(a[i][j]==0)
			ve[v].push_back({u,d}); 
	}
	dijkstra(s);
	if(dis[t]==0x3f3f3f3f){
		cout<<-1<<endl;
	}else{
		cout<<dis[t];
	}
	return 0;
}