Submission #1248974

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248974		trungcan	Cities (BOI16_cities)	C++17	100 / 100	2816 ms	43404 KiB

cities

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pli pair<ll, int>
#define fi first
#define se second

using namespace std;

const int N = 1e5 + 5;
const ll INF = 1e15;

short k;
int n, m, a[6];
ll ans = INF, dp[N][35];
vector<pii> adj[N];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> n >> k >> m;
    for (short i = 0; i < k; ++i) cin >> a[i];
    while (m--){
        int u, v, w; cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    for (short mask = 0; mask < (1 << k); mask++){
        short cnt = __builtin_popcount(mask);
        for (int u = 1; u <= n; ++u){
            dp[u][mask] = INF;
            if (cnt == 1 && a[__builtin_ctz(mask)] == u) dp[u][mask] = 0;
            if (cnt > 1)
                for (short x = (mask - 1) & mask; x > 0; x = (x - 1) & mask)
                    for (pii v: adj[u])
                        dp[u][mask] = min(dp[u][mask], dp[v.fi][x] + dp[u][mask ^ x] + v.se);
        }

        priority_queue<pli, vector<pli>, greater<pli>> q;
        for (int u = 1; u <= n; ++u) q.push({dp[u][mask], u});
        while (!q.empty()){
            int i = q.top().se;
            ll di = q.top().fi; q.pop();
            if (di != dp[i][mask]) continue;
            for (pii v: adj[i])
                if (dp[v.fi][mask] > di + v.se)
                    q.push({dp[v.fi][mask] = di + v.se, v.fi});
        }
    }

    for (int u = 1; u <= n; ++u) ans = min(ans, dp[u][(1 << k) - 1]);

    cout << ans;
}

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