rt，看了一些帖子，大部分都是 T 在了 #10 上，我这 #10 能跑到 5ms 但输出的是一个错误答案。

下载了数据看了一下，不存在文化相互排斥，而且每个国家的文化编号都是互不相同的，在这种情况下难道不就相当于跑最短路吗？为什么标答给的是 -1（无解）

求解惑。或者是我脑子抽了犯了一些奇妙的错误

92pts 记录

用的是反向dijkstra+剪枝深搜

#include <bits/stdc++.h>

#define N 2010
using namespace std;

struct Edge {
    int to, ne, w;
} edges[400010];

typedef pair<int, int> PII;

int idx = 0, ans = 0x3f3f3f3f;
bool modified = false;
int n, m, k, s, t;
int c[N];
int h[N], rh[N];
bool rej[N][N];
priority_queue<PII, vector<PII>, greater<> > q;
int dist[N];
bool st[N], learnt[N];

void add(int he[], int u, int v, int w) {
    idx++;
    edges[idx].to = v;
    edges[idx].ne = he[u];
    edges[idx].w = w;
    he[u] = idx;
}

void dijkstra() {
    q.push((PII) {0, t});
    dist[t] = 0;
    while (!q.empty()) {
        int id = q.top().second;
        int dis = q.top().first;
        q.pop();

        if (st[id]) continue;
        st[id] = true;

        for (int i = rh[id]; ~i; i = edges[i].ne) {
            int j = edges[i].to;
            if (dis + edges[i].w < dist[j]) {
                dist[j] = dis + edges[i].w;
                q.push((PII) {dist[j], j});
            }
        }
    }
}

bool check(int nation) {
    for (int i = 1; i <= k; i++) {
        if (rej[nation][i] && learnt[i]) return true;
    }
    return false;
}

void dfs(int u, int step) {
    if (step + dist[u] >= ans) return;
    if (u == t) {
        if (!check(t) && !learnt[c[t]]) {
            ans = step, modified = true;
            cout<<ans<<endl;
        }
        return;
    }

    for (int i = h[u]; ~i; i = edges[i].ne) {
        int j = edges[i].to;
        if (st[j] || learnt[c[j]] || check(j)) continue;
        st[j] = true;
        learnt[c[i]] = true;
        dfs(j, step + edges[i].w);
        st[j] = false;
        learnt[c[i]] = false;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    memset(h, -1, sizeof h);
    memset(rh, -1, sizeof rh);
    memset(dist, 0x3f, sizeof dist);

    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++) {
            int x;
            cin >> x;
            rej[i][j] = (x == 1);
        }
    }

    for (int i = 1; i <= m; i++) {
        int u, v, d;
        cin >> u >> v >> d;
        add(h, u, v, d);
        add(rh, v, u, d);
    }

    dijkstra();
    memset(st, 0, sizeof st);
    learnt[c[s]] = true;
    dfs(s, 0);
    cout << (modified ? ans : -1) << endl;
    return 0;
}