Submission #1293492

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293492		madamadam3	Cities (BOI16_cities)	C++20	100 / 100	696 ms	32232 KiB

cities

#include <bits/stdc++.h>

using namespace std;
#define int long long int

using pi = pair<int, int>;
const int INF = 4e18;

signed main() {
    cin.tie(0)->sync_with_stdio(0);

    int n, m, k; cin >> n >> k >> m;
    vector<int> imp(k); for (int i = 0; i < k; i++) cin >> imp[i];
    vector<vector<pi>> adj(n+1, vector<pi>());
    for (int i = 0; i < m; i++) {
        int u, v, c; cin >> u >> v >> c;
        adj[u].push_back({v, c});
        adj[v].push_back({u, c});
    }

    vector<vector<int>> DP(1<<(k-1), vector<int>(n+1, INF));
    for (int i = 0; i < k-1; i++) DP[1<<i][imp[i]] = 0;

    for (int mask = 0; mask < (1<<(k-1)); mask++) {
        for (int submask = mask; submask > 0; submask = ((submask - 1) & mask)) {
            int left = submask, right = mask ^ submask;
            if (left > right) continue; // evaluate each pair once

            for (int i = 1; i <= n; i++) {
                DP[mask][i] = min(DP[mask][i], DP[left][i] + DP[right][i]);
            }
        }

        priority_queue<pi, vector<pi>, greater<pi>> pq;
        vector<bool> vis(n+1, false);

        for (int i = 1; i <= n; i++) pq.push({DP[mask][i], i});
        while (!pq.empty()) {
            int u = pq.top().second; pq.pop();
            if (vis[u]) continue;
            vis[u] = true;

            for (auto el : adj[u]) {
                int d = DP[mask][u] + el.second;
                if (d < DP[mask][el.first]) {
                    DP[mask][el.first] = d;
                    pq.push({d, el.first});
                }
            }
        }
    }

    cout << DP[(1<<(k-1))-1][imp[k-1]] << "\n"; // min(DP[(1<<k)-1][x]) = min cost to connect all imp to some x = min cost to connect
    return 0;                                   // first k-1 imp to the kth imp
}

• Subtask 1: 22 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 26 / 26