蓝桥杯算法提高VIP-文化之旅 （C++代码）

解题思路:





注意事项:





参考代码:

麻烦的要死：

#include<bits/stdc++.h>
using namespace std;
int z[150]/*每种文化是否已学习或被排斥，-1学习，大于0排斥*/,n/*国家数量*/,k/*文化数量*/,m/*道路数量*/;int from/*起点*/,want/*终点*/,s[120][120]/*文化之间的排斥情况，后者为被排斥*/,q[120][120]/*两个国家之间的距离*/; 
int ans=9999999,may,have[120]/*每个国家所拥有的文化*/;
void search(int now)
{    
int i,j;    
if(now==want)//如果到了
    {        
if(may<ans) ans=may;//小就更新
        return ;
    }    
if(may>=ans) return ;//剪枝
    for(i=1;i<=n;i++)
    {        if(q[now][i]!=9999999&&z[have[i]]==0)//如果能到，并且文化不排斥不重复
        {
            may+=q[now][i];
            z[have[i]]=-1;            
            for(j=1;j<=n;j++)                
            if(s[have[j]][i]) z[j]++;//这里注意是学习过被当地排斥的文化才不能进，之前搞反了全输出-1.。。这里要用++是因为回溯的时候如果直接用的是true或1的话，万一这个文化被很多地方排斥，而那些地方也排斥了其他文化，那么可能学习过好几种被某个地方排斥的文化，这样回溯掉一种显然也是不能去的，所以不能完全消掉，因此用++来表示，回溯就--，可以就不会去掉其他文化导致的不能去了
            search(i);
            may-=q[now][i];//回溯
            z[have[i]]=0;            
            for(j=1;j<=n;j++)                
            if(s[have[j]][i]) z[j]--;
        }
    } 
}int main()
            {    
            int a,b,c,j,i;    
            memset(z,0,120);    
            scanf("%d%d%d%d%d",&n,&k,&m,&want,&from);//反着读，就相当于倒着搜索，，会快一点（但是某一个点会慢一点），我也不知道为什么
    for(i=1;i<=n;i++)
    {        scanf("%d",&have[i]);        
            for(j=1;j<=n;j++)
            q[i][j]=9999999;
    }    for(i=1;i<=k;i++)       
             for(j=1;j<=k;j++)
        {
            s[i][j]=false;            
             scanf("%d",&b);            
             if(!b)continue;
            s[i][j]=true;        
        }    for(i=1;i<=m;i++)
    {        scanf("%d%d%d",&a,&b,&c);        
        if(q[a][b]>c) q[a][b]=c; 
        if(q[b][a]>c) q[b][a]=c;
    } 
    z[have[from]]=-1;    
        for(i=1;i<=n;i++)        
        if(s[i][have[from]]) z[i]++;
    search(from);    
        if(ans==9999999) ans=-1;//如果ans没有被改变过，就代表不能到
    printf("%d",ans);    
        return 0; 
}