我认为这道题不一定是什么搜索什么剪枝吧，虽然题目出错了orz

我觉得可以把这道题看作分层图来跑，以 已经学习了的文化 为状态，配合Dijkstra的贪心策略解答，bitset来存储状态，每次拓展边时判断是否矛盾再q.push()。

当然我的做法也不能保证正确性，可能有错误欢迎指出，如果有hack数据的话那么多多益善orz

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e2+5;
int n,m,k,s,t;
int c[maxn];
bitset<maxn> a[maxn];
int fst[maxn],L = 1;
int dis[maxn];
bool vis[maxn];
struct Node{
	int v;
	int len;
	bitset<maxn> bit;
	bool operator<(const Node &temp)const{
		return len > temp.len;
	}
};
struct Edge{
	int v;
	int w;
	int next;
}edges[20005];
void addedge(int u,int v,int w){
	edges[L].w = w;
	edges[L].v = v;
	edges[L].next = fst[u];
	fst[u] = L++;
}
priority_queue<Node> q;
void Dijkstra(int s){
	bitset<maxn> bits;
	bits[c[s]] = 1;
	dis[s] = 0;
	q.push({s,0,bits});
	while(!q.empty()){
		Node cur = q.top();
		q.pop();
		int u = cur.v;
		if(vis[u]) continue;
		vis[u] = true;
		
		for(int p = fst[u]; p ; p = edges[p].next){
			int w = edges[p].w;
			int v = edges[p].v;
			bitset<maxn> temp = cur.bit; 
			bitset<maxn> next = (a[c[v]] & temp);
			if(next.any() || temp[c[v]]) continue;
			
			temp[c[v]] = 1;
			if(dis[u] + w < dis[v]){
				dis[v] = dis[u] + w;
				q.push({v,dis[v],temp});
			}
		}
	}
}
int main(){
	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;i<=k;i++){
		for(int j=1;j<=k;j++){
			int temp;
			scanf("%d",&temp);
			a[i][j] = temp;
		}
	}
	int x,y,w;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&w);
		addedge(x,y,w);
		addedge(y,x,w);
	}
	for(int i=1;i<=n;i++){
		dis[i] = INT_MAX;
	}
	Dijkstra(s);
	if(dis[t] == INT_MAX){
		printf("-1\n");
	}else{
		printf("%d\n",dis[t]);
	}
	return 0;
}
/*
in:
3 2 3 1 3
1 2 1
0 0
0 0
1 2 1
1 3 1
2 3 1
out:
-1
*/