补给计划(Supply Plan) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <functional>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, k;
    if (!(cin >> n >> m >> k)) return 0;
    vector<int> can(n + 1);
    for (int i = 1; i <= n; ++i) cin >> can[i];
    vector<int> x(k);
    for (int i = 0; i < k; ++i) cin >> x[i];
    vector<vector<pair<int, long long>>> adj(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    const long long INF = (1LL << 60);
    auto dijkstra = [&](int src) {
        vector<long long> d(n + 1, INF);
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
        d[src] = 0;
        pq.push({0, src});
        while (!pq.empty()) {
            auto top = pq.top();
            pq.pop();
            long long du = top.first;
            int u = top.second;
            if (du > d[u]) continue;
            for (auto& edge : adj[u]) {
                int v = edge.first;
                long long w = edge.second;
                if (d[u] + w < d[v]) {
                    d[v] = d[u] + w;
                    pq.push({d[v], v});
                }
            }
        }
        return d;
    };
    vector<long long> d1 = dijkstra(1);
    vector<vector<long long>> dx(k);
    for (int i = 0; i < k; ++i) dx[i] = dijkstra(x[i]);
    vector<int> masks;
    for (int v = 1; v <= n; ++v) {
        if (!can[v] || d1[v] >= INF) continue;
        int mask = 0;
        for (int i = 0; i < k; ++i) {
            if (d1[v] + dx[i][v] == d1[x[i]]) {
                mask |= (1 << i);
            }
        }
        if (mask > 0) masks.push_back(mask);
    }
    sort(masks.begin(), masks.end());
    masks.erase(unique(masks.begin(), masks.end()), masks.end());
    vector<int> filtered;
    for (size_t i = 0; i < masks.size(); ++i) {
        bool sub = false;
        for (size_t j = 0; j < masks.size(); ++j) {
            if (i != j && (masks[i] & masks[j]) == masks[i]) {
                sub = true;
                break;
            }
        }
        if (!sub) filtered.push_back(masks[i]);
    }
    vector<vector<int>> covers(k);
    for (int mask : filtered) {
        for (int b = 0; b < k; ++b) {
            if ((mask >> b) & 1) covers[b].push_back(mask);
        }
    }
    int full = (1 << k) - 1;
    int best = k;
    auto dfs = [&](auto& self, int cur_mask, int cnt) -> void {
        if (cnt >= best) return;
        if (cur_mask == full) {
            best = cnt;
            return;
        }
        int pick_b = -1;
        int min_ways = 1000000;
        for (int b = 0; b < k; ++b) {
            if (!((cur_mask >> b) & 1)) {
                int ways = covers[b].size();
                if (ways < min_ways) {
                    min_ways = ways;
                    pick_b = b;
                }
            }
        }
        vector<int> cands = covers[pick_b];
        int rem = full ^ cur_mask;
        sort(cands.begin(), cands.end(), [&](int a, int b) {
            return __builtin_popcount(a & rem) > __builtin_popcount(b & rem);
        });
        for (int m_val : cands) {
            self(self, cur_mask | m_val, cnt + 1);
        }
    };
    dfs(dfs, 0, 0);
    cout << best << "\n";
    return 0;
}