第一版

#include <iostream>
#include <cstring>
#include <queue>
#include <map>

#define x first
#define y second

using namespace std;

typedef pair<int,int> PII;
const int N = 310;
int culture[N];
int n,k,m,s,t;
int g[N][N];
int d[N];
int way[N];
vector<int> re[N];

bool check(int point,int x){
    int c = point;
    int cc = point;
    while (c != s){
        for (int j = 0;j < re[x].size();j ++){
            if (culture[c] == re[x][j]) return true;
        }
        c = way[c];
        if (culture[cc] == culture[c]) return true;
    }
    for (int i = 0;i < re[x].size();i ++){
        if (culture[s] == re[x][i]) return true;
    }
    if (culture[cc] == culture[s]) return true;

    return false;
}

void dijkstra(){
    memset(d,0x3f,sizeof d);
    priority_queue<PII,vector<PII>,greater<PII>> q;
    q.push({0,s});
    d[s] = 0;

    while (q.size()){
        auto tt = q.top();
        q.pop();

        if (tt.y == t){
            cout << d[tt.y] << endl;
            return;
        }
        for (int i = 1;i <= n;i ++){
            if (tt.y == i) continue;
            if (g[tt.y][i] == 0x3f3f3f3f) continue;
            if (tt.x + g[tt.y][i] >= d[i]) continue;

            way[i] = tt.y;
            if (check(i,culture[i])) continue;

            d[i] = tt.x + g[tt.y][i];
            q.push({d[i],i});
        }
    }
    cout << "-1" << endl;
    return;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    memset(g,0x3f,sizeof g);
    cin >> n >> k >> m >> s >> t;
    for (int i = 1;i <= n;i ++) cin >> culture[i];

    for (int i = 1;i <= k;i ++)
        for (int j = 1;j <= k;j ++){
            int x;
            cin >> x;
            if (x == 1) re[i].push_back(j);
        }

    for (int i = 1;i <= m;i ++){
        int u,v,d;
        cin >> u >> v >> d;
        g[u][v] = g[v][u] = min(g[u][v],d);
    }

    dijkstra();

    return 0;
}

第一个在luogu,acwing都能过,第二个只能在acwing过

第二版

#include <iostream>
#include <cstring>
#include <queue>
#include <map>
#include <bitset>

#define x first
#define y second

using namespace std;

typedef pair<int,int> PII;
const int N = 310;
int culture[N];
int n,k,m,s,t;
int g[N][N];
int d[N];
bitset<N> has[N]; //用bitset来存到i城市之前的文化有没有学习过，学习过则存为1,未学习则是0
vector<int> re[N];

bool check(int point,int x){
    for (int i = 0;i < re[x].size();i ++){
        if (has[point][x] == 1 || has[point][re[x][i]]) return true;
        else return false;
    }
}

void dijkstra(){
    memset(d,0x3f,sizeof d);
    priority_queue<PII,vector<PII>,greater<PII>> q;
    q.push({0,s});
    has[s][culture[s]] = 1;
    d[s] = 0;

    while (q.size()){
        auto tt = q.top();
        q.pop();

        if (tt.y == t){
            cout << d[tt.y] << endl;
            return;
        }
        for (int i = 1;i <= n;i ++){
            if (tt.y == i) continue;
            if (g[tt.y][i] == 0x3f3f3f3f) continue;
            if (tt.x + g[tt.y][i] >= d[i]) continue; //一个点可能被遍历多次，只要长度大于该点就直接略过

            has[i] = has[tt.y];
            if (has[i][culture[i]]) continue; //如果到第i个城市之前该文化已经学习过，则直接略过
            has[i][culture[i]] = 1; //没有则将该路径的文化置为1
            if (check(i,culture[i])) continue;

            d[i] = tt.x + g[tt.y][i];
            q.push({d[i],i});
        }
    }
    cout << "-1" << endl;
    return;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    memset(g,0x3f,sizeof g);
    cin >> n >> k >> m >> s >> t;
    for (int i = 1;i <= n;i ++) cin >> culture[i];

    for (int i = 1;i <= k;i ++)
        for (int j = 1;j <= k;j ++){
            int x;
            cin >> x;
            if (x == 1) re[i].push_back(j); //将第i个文化排斥第j个文化加入进去
        }

    for (int i = 1;i <= m;i ++){
        int u,v,d;
        cin >> u >> v >> d;
        g[u][v] = g[v][u] = min(g[u][v],d); //题目两点之间可能有多条道路，选择最短的
    }

    dijkstra();

    return 0;
}