蓝桥杯算法提高VIP-文化之旅 （C++代码）逆向DFS搜索+剪枝

解题思路:

注意事项:

参考代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<set>
#include<cmath>
#include<algorithm>
using namespace std;

const int N=110,K=110;
int c[N],cultrul[K],graph[N][N],vis[N],a[N][N];
int n,k,m,s,t;
long long res=-1;
set<int>cu;

void dfs(int next,long long sum)
{
    if(res!=-1 && sum>res) return ;
    if(next==s)
    {
    	if(res==-1) res=sum;
		else res=min(res,sum);//记录更短的路径
        return ;    
    } 
    for(int i=1;i<=n;i++)
    {
        //没有来过这个国家  路径走得通  没有学习过这类文化  
        if(!vis[i] && graph[i][next] && cultrul[c[i]]==false)
        {
            bool ok=true;
            for(set<int>::iterator it=cu.begin();it!=cu.end();it++)//枚举后面国家文化类型 
            {
                if(a[c[i]][*it])//如果当前国家文化和后继国家文化冲突 
                {
                    ok=false;
                    break;
                }
            }
            if(ok)
            {
                vis[i]=true;
                cultrul[c[i]]=true;
                cu.insert(c[i]);
                dfs(i,sum+graph[i][next]);
                vis[i]=false;
                cultrul[c[i]]=false;
                cu.erase(c[i]);
            }
        }   
    } 
} 
int main(void)
{
    //freopen("D:\\input6.txt","r",stdin);
    int u,v,d;
    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>>d;
        if(graph[u][v]==0) graph[u][v]=graph[v][u]=d;
        else if(graph[u][v]>d)
        {
            graph[u][v]=graph[u][v]=d;
        }
    }
    
    vis[t]=true;//访问过这个国家 
    cultrul[c[t]]=true;//学习了这种文化 
    cu.insert(c[t]); 
    dfs(t,0);
    cout<<res;
    return 0;
}