rt，我首先写出来一个暴力dfs，然后不出所料地T了4个点

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e2+5,inf=0x3f3f3f3f;
int n,k,m,s,t,path[maxn][maxn],counc[maxn],ans=inf;
bool cult[maxn][maxn],vst[maxn],learnt[maxn];
inline int get_min(int a,int b){
	return a<b?a:b;
}
void dfs(int pos,int sum){
	if(pos==t){
		ans=get_min(ans,sum);
		return;
	}
	for(int i=1;i<=n;i++){
		if(vst[i]||path[pos][i]==inf) continue;
		bool flag=true;
		for(int j=1;j<=k;j++)
			if(learnt[j]&&cult[counc[i]][j]){
				flag=false;
				break;
			}
		if(!flag) continue;
		learnt[counc[i]]=vst[i]=true;
		dfs(i,sum+path[pos][i]);
		learnt[counc[i]]=vst[i]=false;
	}
	return;
}
int main(){
	scanf("%d%d%d%d%d",&n,&k,&m,&s,&t);
	memset(path,0x3f,sizeof(path));
	for(int i=1;i<=n;i++) scanf("%d",counc+i);
	for(int i=1;i<=k;i++)
		for(int j=1;j<=k;j++){
			scanf("%d",&cult[i][j]);
			if(i==j) cult[i][j]=true;
		}
	while(m--){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		path[u][v]=path[v][u]=get_min(path[u][v],w);
	}
	learnt[counc[s]]=vst[s]=true;
	dfs(s,0);
	printf("%d",ans==inf?-1:ans);
	return 0;
}

然后就非常难受，我怎么都想不到合理的优化方案，然后我灵（qi）光（ji）一（bai）现（huai），尝（luan）试（gao）删了dfs的回溯操作，然后就就就A了。

真的真的就是删了一行回溯，你想想dfs删了回溯会变成什么？AC代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e2+5,inf=0x3f3f3f3f;
int n,k,m,s,t,path[maxn][maxn],counc[maxn],ans=inf;
bool cult[maxn][maxn],vst[maxn],learnt[maxn];
inline int get_min(int a,int b){
	return a<b?a:b;
}
void dfs(int pos,int sum){
	if(pos==t){
		ans=get_min(ans,sum);
		return;
	}
	for(int i=1;i<=n;i++){
		if(vst[i]||path[pos][i]==inf) continue;
		bool flag=true;
		for(int j=1;j<=k;j++)
			if(learnt[j]&&cult[counc[i]][j]){
				flag=false;
				break;
			}
		if(!flag) continue;
		learnt[counc[i]]=vst[i]=true;
		dfs(i,sum+path[pos][i]);
//		learnt[counc[i]]=vst[i]=false;
	}
	return;
}
int main(){
	scanf("%d%d%d%d%d",&n,&k,&m,&s,&t);
	memset(path,0x3f,sizeof(path));
	for(int i=1;i<=n;i++) scanf("%d",counc+i);
	for(int i=1;i<=k;i++)
		for(int j=1;j<=k;j++){
			scanf("%d",&cult[i][j]);
			if(i==j) cult[i][j]=true;
		}
	while(m--){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		path[u][v]=path[v][u]=get_min(path[u][v],w);
	}
	learnt[counc[s]]=vst[s]=true;
	dfs(s,0);
	printf("%d",ans==inf?-1:ans);
	return 0;
}

虽然通过题面题解和评论区我已经初步了解到了这道提的离谱之处，但是我真的真的没想到能有这么离谱