链接

dfs+模拟

#include <bits/stdc++.h>
using namespace std;
struct con{
	int next;
	int w; 
};
int n,k,m,sp,ep,culture[1001],c2,c1,c3,f[1001],hatec[1001][1001];
vector<con> v[1001];
vector<int> me;//存我学过的文化
void dfs(int k,int s);
int main(){
	cin >> n >> k >> m >> sp >> ep;\
	memset(f,0X3f,sizeof(f));
	for(int i = 1;i <= n;i++){
		cin >> c1;
		culture[i] = c1;//存文化 
	}
	for(int i = 1;i <= k;i++){ 
		for(int j = 1;j <= k;j++){
			cin >> c1;
			hatec[i][j] = c1;//存文化歧视链
		}
	}
	for(int i = 1;i <= m;i++){
		cin >> c1 >> c2 >> c3;
		con in; in.next = c2,in.w = c3;
		v[c1].push_back(in);//存图 
	}
	dfs(sp,0);
	if(f[ep] == 1061109567) f[ep] = -1;
	cout << f[ep];
	return 0;
} 
void dfs(int k,int s){
	if(f[k] >= s) f[k] = s;//记忆化 
	else return; 
	if(k == ep) return;//到达 
	me.push_back(culture[k]);//存我学过的文化 
	for(int i = 0;i <= (int)v[k].size()-1;i++)
		for(int j = 0;j <= (int)me.size()-1;j++)
			if(me[j] != culture[v[k][i].next] && !hatec[culture[v[k][i].next]][me[j]])//如果 是我没学过的文化 并且 那个国家不歧视我 
				if(f[v[k][i].next] == 1061109567/*0X3f*/)//没去过 
					dfs(v[k][i].next,s+v[k][i].w);				
}