本篇题解提供了一种可以得65分的bfs做法,如想看则正解,请转步

思路:

用一个set记录当前学习了那些文化,其他几乎都是正常

Code

#include<bits/stdc++.h>
using namespace std;
const int N=110,M=2e4+10,INF=0x3f3f3f3f;
int n,m,k,s,terminal,c[N],idx,h[N],e[M],ne[M],w[M];
map<set<int>,int>dist;
bool st[N][N];
struct Q{
    int num;
    set<int>se;
};
void add(int a,int b,int c){
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
bool check(Q t,int x){
    if(t.se.count(c[x])) return false; //当前这种文化学过了
    for(auto WH:t.se){
        if(st[c[x]][WH]) return false; //当前排斥这种文化
    }
    return true;
}
int bfs(){
    queue<Q>q;
    set<int>temp;
    temp.insert(c[s]);
    q.push({s,temp});
    int res=INF;
    dist[temp]=0;
    while(!q.empty()){
        Q t=q.front();
        q.pop();
        if(t.num==terminal){
            res=min(res,dist[t.se]);
            continue;
        }
        for(int i=h[t.num];i!=-1;i=ne[i]){
            int j=e[i];
            if(!check(t,j)) continue;
            set<int>tmp=t.se;
            tmp.insert(c[j]);
            if(!dist.count(tmp)) dist[tmp]=INF;
            if(dist[tmp]>dist[t.se]+w[i]){
                dist[tmp]=dist[t.se]+w[i];
                q.push({j,tmp});
            }
        }
    }
    return (res==INF?-1:res);
}
int main(){
    cin>>n>>k>>m>>s>>terminal;
    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>>st[i][j];
        }
    }
    memset(h,-1,sizeof h);
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    cout<<bfs();
    return 0;
}