easy！！

2013zry · 2024-11-16 20:05:51 · 题解

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <climits>

using namespace std;

const int N = (1 << 12) + 5;
const int INF = 0x7fffffff;

int n, m, K, s, t1, t2, t3, st;
int cnt[N]; // cnt[i]储存状态i可以得到的成就
int trs[15], ned[15]; // trs[i]储存宝藏编号为i的对应点，ned[i]储存宝藏i的前提条件
int req[15], rwd[15]; // 成就的前提和奖励
int flo[205][205]; // 存储点之间的距离
bool vis[15][N][15]; // 广搜记忆数组

struct Node {
    int p, zt, lef, stp;
    bool operator >(const Node &tmp) const {
        return stp > tmp.stp;
    }
};

priority_queue<Node, vector<Node>, greater<Node>> q;

inline int count(int x) {
    int ret = 0;
    for (int i = 1; i <= s; ++i) {
        if ((x & req[i]) == req[i]) {
            ret += rwd[i];
        }
    }
    return ret;
}

int bfs() {
    for (int i = 0; i < (1 << m); ++i) cnt[i] = count(i);
    for (int i = 1; i <= m; ++i) {
        int nzt = (1 << (i - 1));
        if (ned[i] == 0) {
            if (trs[i] != st && K >= 1) {
                vis[i][nzt][K - 1 + cnt[nzt]] = true;
                q.push({i, nzt, K - 1 + cnt[nzt], 0});
            }
            q.push({i, nzt, K + cnt[nzt], flo[st][trs[i]]});
            vis[i][nzt][K + cnt[nzt]] = true;
        }
    }
    while (!q.empty()) {
        int np = q.top().p, nz = q.top().zt, nl = q.top().lef, nstep = q.top().stp;
        vis[np][nz][nl] = true;
        if (nz == (1 << m) - 1) return nstep;
        q.pop();
        t1 = cnt[nz];
        for (int i = 1; i <= m; ++i) {
            if (np == i || (nz & ned[i]) != ned[i] || (nz & (1 << (i - 1))) != 0) continue;
            int nxt = nz ^ (1 << (i - 1));
            t2 = cnt[nxt];
            if (!vis[i][nxt][nl + (t2 - t1)]) q.push({i, nxt, nl + (t2 - t1), nstep + flo[trs[np]][trs[i]]});
            if (nl >= 1 && !vis[i][nxt][nl - 1 + (t2 - t1)]) q.push({i, nxt, nl - 1 + (t2 - t1), nstep});
        }
    }
    return 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    memset(flo, 0x3f, sizeof(flo));
    cin >> n >> m >> K >> s;
    for (int i = 1; i <= n; ++i) flo[i][i] = 0;
    for (int i = 1; i <= s; ++i) {
        cin >> t1;
        for (int j = 1; j <= t1; ++j) {
            cin >> t2;
            req[i] |= (1 << (t2 - 1));
        }
    }
    for (int i = 1; i <= s; ++i) cin >> rwd[i];
    for (int i = 1; i <= m; ++i) cin >> trs[i];
    cin >> t1;
    for (int i = 1; i <= t1; ++i) {
        cin >> t2 >> t3 >> t1;
        flo[t2][t3] = flo[t3][t2] = min(flo[t2][t3], t1);
    }
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                flo[i][j] = min(flo[i][j], flo[i][k] + flo[k][j]);
            }
        }
    }
    for (int i = 1; i <= m; ++i) {
        cin >> t1;
        for (int j = 1; j <= t1; ++j) {
            cin >> t2;
            ned[i] |= (1 << (t2 - 1));
        }
    }
    cin >> st;
    cout << bfs();
    return 0;
}

求赞！