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

解题思路:

注意事项:

参考代码:

// s 和t反过来就可以ac 不然会超时

#include<iostream>
#include<set>
#include<vector>
using namespace std;
int grap[101][101];
vector<int > upset[101];    //存储文化之间的关系
int culture[101];//存储每个国家的文化
int n,k,m,s,t;
set<int> cul; //已经学了的文化
int cost=10000007;
bool findx(int x){
    for(int i=0;i<upset[x].size();i++){
        if(cul.count(upset[x][i])){
            return false;
        }
    }
    return true;
}
void dfs(int x,int sum){    //当前在x国家
    if(sum>=cost){
        return;
    }
    if(x==t){
        cost = min(cost,sum);
        return ;
    }
    for(int i=1;i<=n;i++){
        int cc = culture[i];
        if(!cul.count(cc)&&grap[x][i]!=0&&findx(cc)){
            cul.insert(cc);
            dfs(i,sum+grap[x][i]);
            cul.erase(cc);
        }
    }
}
int main(){
    cin>>n>>k>>m>>t>>s;
    for(int i=1;i<=n;i++)
        scanf("%d",&culture[i]);
    int t;
    for(int i=1;i<=k;i++){
        for(int j=1;j<=k;j++){
            scanf("%d",&t);
            if(t==1){
                upset[i].push_back(j);
            }
        }
    }
    int a,b,c;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&a,&b,&c);
        int x = grap[a][b];
        if(x!=0&&x<c){
        }
        else{
            grap[a][b] = c;
            grap[b][a] = c;
        }
    }
    cul.insert(culture[s]);
    dfs(s,0);
    if(cost!=10000007)
        cout<<cost;
    else
        cout<<-1;
    return 0;
}