Submission #1131009

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131009		RandomUser	Cities (BOI16_cities)	C++20	74 / 100	6086 ms	137980 KiB

cities

#include <bits/stdc++.h>
#define ar array
using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int maxn = 1e5 + 5;
const ll INF = 1e18;

ll dist[5][maxn], dp[1<<5][maxn], imp[5];
vector<pii> G[maxn];

void dijkstra(int src, ll dist[]) {
    priority_queue<pll, vector<pll>, greater<>> pq;
    fill(dist, dist + maxn, INF);
    dist[src] = 0;
    pq.push({0, src});
    
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (dist[u] < d) continue;
        for (auto [v, w] : G[u]) {
            if (dist[v] > d + w) {
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);

    int n, k, m;
    cin >> n >> k >> m;
    for (int i = 0; i < k; i++) {
        cin >> imp[i];
    }

    for (int i = 1; i <= m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        G[a].push_back({b, w});
        G[b].push_back({a, w});
    }

    // Step 1: Run Dijkstra from each important node
    for (int i = 0; i < k; i++) {
        dijkstra(imp[i], dist[i]);
    }

    // Step 2: Multi-source DP with state compression
    priority_queue<ar<ll, 3>, vector<ar<ll, 3>>, greater<>> pq;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < (1 << k); j++) {
            dp[j][i] = INF;
        }
    }

    for (int i = 0; i < k; i++) {
        dp[1 << i][imp[i]] = 0;
        pq.push({0, imp[i], 1 << i});
    }

    while (!pq.empty()) {
        auto [d, u, s] = pq.top(); pq.pop();
        if (d != dp[s][u]) continue;
        
        // Relax edges with the same bitmask
        for (auto [v, w] : G[u]) {
            if (dp[s][v] > d + w) {
                dp[s][v] = d + w;
                pq.push({dp[s][v], v, s});
            }
        }

        // Relax states by adding another important node
        for (int i = 0; i < k; i++) {
            int newState = s | (1 << i);
            if (dp[newState][u] > d + dist[i][u]) {
                dp[newState][u] = d + dist[i][u];
                pq.push({dp[newState][u], u, newState});
            }
        }
    }

    ll ans = INF;
    for (int i = 1; i <= n; i++) {
        ans = min(ans, dp[(1 << k) - 1][i]);
    }
    cout << ans << '\n';

    return 0;
}

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