考虑使用搜索 dfs。

当 $u\to v$ 的一条边建立成功时，仅当 $v$ 国的文化认可 $u$ 国的文化。

因为可能有重边，所以比最小值。

当 $s$ 国和 $t$ 国的文化相同，明显不可能成为一种方案，直接输出 $-1$，结束。

然后就是一个 dfs 模板，剪枝为当前到达 $x$ 国的距离 $sum$ 大于等于 $dis_x$（到当前到达 $x$ 国的最小值）。

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define rrep(i,x,y) for(int i=x;i>=y;i--)
#define sc scanf
#define pr printf
#define inf 1e9
#define endline pr("\n")

inline int read() {
	int s = 0, w = 1;
	char c = getchar();
	while (!isdigit(c)) {
		if (c == '-') w = -1;
		c = getchar();
	}
	while (isdigit(c)) {
		s = (s << 1) + (s << 3) + (c ^ 48);
		c = getchar();
	}
	return s * w;
}

const int N=105;
int n,k,m,s,t,ans = 0x3f3f3f , dis[N];
vector <int> edge[N];
bool vis[N] , visit[N];
int c[N] , E[N][N] , w[N][N];

inline void dfs(int x,int sum){
  if(sum >= dis[x]) return;
  dis[x] = sum;
  if(x == t){
    ans = min(ans, dis[x]);
    return;
  }
  for(auto i : edge[x]){
   if(!visit[c[i]]){//没有访问过的文化。
      visit[c[i]] = true;
      dfs(i , sum + w[x][i]);
      visit[c[i]] = false;
   }
  }

}

signed main() {
  memset(dis,0x3f3f3f,sizeof dis);
  n=read();k=read();m=read();s=read();t=read();
  rep(i,1,n) c[i] = read();

  rep(i,1,k)
    rep(j,1,k) scanf("%lld",&E[i][j]);

  rep(i,1,n) rep(j,1,n) if(i != j) w[i][j] = inf;
  rep(i,1,m){
    int u = read() , v = read() , d = read();
    if(!E[c[v]][c[u]]) edge[u].push_back(v) , w[u][v] = min(w[u][v] , d);
    if(!E[c[u]][c[v]]) edge[v].push_back(u) , w[v][u] = min(w[v][u] , d);//建边。
  }

  if(c[s] == c[t]){
    pr("-1\n");
    exit(0);
  }
  dfs(s,0);
  if(ans != 0x3f3f3f) pr("%lld\n",ans);
  else pr("-1\n");
  return 0;
}

$floyd$ 更简单，$\Theta (n^3)$ 也不会 T。

普通 $floyd$ 肯定过不了，因为有的边不可以连接。

因此特判两条边是否可以连接，如果 $u$ 能够连接向 $v$，那么 $v$ 国必须认可 $u$ 国的文化，即 $b_{v,u} = 0$；反过来，对于 $v$ 连接向 $u$，必须满足 $b_{u,v} = 0$。

如果可以连接，注意比最小值，因为由重边。

最后跑一边 $floyd$ 即可。

注：如果 $s$ 国和 $t$ 国的文化相同，直接输出 $-1$，需要特判。

#include <iostream>
#include <cstdio>

using namespace std;
#define int long long
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define rrep(i,x,y) for(int i=x;i>=y;i--)
#define pr printf
inline int read(){int s=0,w=0;char c=getchar();while(!isdigit(c)){w|=(c=='-');c=getchar();}while(isdigit(c)){s=(s<<1)+(s<<3)+(c^48);c=getchar();}return w?-s:s；}

const int N=105;
int n,k,m,s,t,a[N],b[N][N],dis[N][N];

signed main(){
  n=read();k=read();m=read();s=read();t=read();
rep(i,1,n) rep(j,1,n) if(i!=j) dis[i][j]=0x3f3f3f3f;//floyd 初始化。
  rep(i,1,n) a[i]=read();
  rep(i,1,k) rep(j,1,k) scanf("%lld",&b[i][j]);
  if(a[s]==a[t]){
  	pr("-1\n");exit(0);
  }
  while(m--){
  	int u=read(),v=read(),d=read();
  	if(!b[a[v]][a[u]]) dis[u][v]=min(dis[u][v],d);
  	if(!b[a[u]][a[v]]) dis[v][u]=min(dis[v][u],d);//可以建边。
  }
rep(k,1,n)
  rep(i,1,n)
    rep(j,1,n) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);//跑 floyd。
  if(dis[s][t]==0x3f3f3f3f) pr("-1\n");
  else pr("%lld\n",dis[s][t]);
  return 0;  
}

启发式大法师

#include <bits/stdc+.h>
using namespace std;
const int N = 2005;
struct node {
	int v, w;
	node(int _, int __) :
		v(_), w(__) {}
};
int c[N], dis[N], sol, n, m, k, s, t, u, v, w, ans = INT_MAX;
bool a[N][N], vis[N], vis1[N];
vector<node> G[N];
vector<int> d, d1;
void SPFA(int s) {
	memset(dis, 0x3f, sizeof dis);
	queue<int> q; q.push(s), dis[s] = 0;
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (node v : G[u])
			if (dis[v.v] > dis[u] + v.w)
				dis[v.v] = dis[u] + v.w, q.push(v.v);
	}
}
void dfs(int u, int sum) {
	if (sum + dis[u] >= ans) return；
	for (int i : d)
		if (a[c[u]][i] || c[u] == i) return;
	if (u == t) return (void)(ans = min(ans, sum));
	d.push_back(c[u]);
	vis[u] = true;
	for (node v : G[u])
		if (!vis[v.v]) dfs(v.v, sum + v.w);
	d.pop_back();
	vis[u] = flase;
}
void dfs2(int u) {
	for (int i : d1) 
		if (a[c[u]][i] || c[u] == i) return;
	if (u == t) return (void)(sol = true);
	d1.push_back(c[u]);
	vis1[u] = true;
	for (node v : G[u])
		if (!vis1[v.v]) dfs2(v.v);
	d1.pop_back();
}
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 i = 1; i <= m; i ++)
		cin >> u >> v >> w, G[u].push_back(node(v, w)), G[v].push_back(node(u, w));
	SPFA(t), dfs2(s);
	if (!sol) puts("-1");
	else dfs(s, 0), cout << ans < '\n';
	return 0;
}