Submission #1278756

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278756		Canuc80k	Cities (BOI16_cities)	C++20	37 / 100	1259 ms	8664 KiB

cities

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll N = 1e3 + 1;

ll n, k, m;
ll a[N], f[(1ll << 5)][N];
vector<array<ll, 2>> g[N];
ll cost[N][N];

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

    cin >> n >> k >> m;
    for (int i = 1; i <= k; i ++) 
        cin >> a[i], a[i] --;

    for (int i = 1; i <= m; i ++) {
        ll u, v, k; cin >> u >> v >> k;
        u --; v --;
        g[u].push_back({v, k});
        g[v].push_back({u, k});
    }

    memset(cost, 0x3f, sizeof cost);
    for (int i = 0; i < n; i ++) {
        cost[i][i] = 0;
        for (auto [u, w]: g[i])
            cost[i][u] = w;  
    }
    for (int k = 0; k < n; k ++)
        for (int i = 0; i < n; i ++)
            for (int j = 0; j < n; j ++)
                if (cost[i][k] <= 1e18 && cost[k][j] <= 1e18)
                    cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);

    memset(f, 0x3f, sizeof f);
    for (int i = 1; i <= k; i ++) f[(1ll << (i - 1))][a[i]] = 0;
    for (int i = 0; i < n; i ++) f[0][i] = 0;
    for (int mask = 0; mask < (1ll << k); mask ++) {
        if (mask == 0) continue;
        for (int submask = mask;; submask = (submask - 1) & mask) {
            for (int u = 0; u < n; u ++) {
                int other = mask ^ submask;
                for (int v = 0; v < n; v ++) {
                    f[mask][u] = min(f[mask][u], f[submask][u] + cost[u][v] + f[other][v]);
                }
                // cout << "Debug: " << mask << ' ' << u << ' ' << f[mask][u] << endl; 
            }
            if (submask == 0) break;
        }
    }

    ll res = 1e18;
    for (int i = 0; i < n; i ++) res = min(res, f[(1ll << k) - 1][i]);
    cout << res;
}

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