Submission #1245839

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245839		dprto	Cities (BOI16_cities)	C++20	100 / 100	1652 ms	57932 KiB

cities

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
#define F(i, l, r) for(int i = l; i <= r; ++i)
#define E(i, l, r) for(int i = l; i >= r; --i)
#define MASK(i) (1 << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define eb emplace_back
const ll mod = 1e9 + 7;
const int ars = 5e5 + 5;
const ll il = 1e18;
const int lim = 1000000;

int n, m, k, a[7], f[ars][37], res = il;
vector<pair<int, int>> adj[ars];

void prep() {
    cin >> n >> k >> m;
    F(i, 1, k) cin >> a[i];
    F(i, 1, m) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].eb(v, w);
        adj[v].eb(u, w);
    }
    F(i, 1, n) F(j, 0, 32) f[i][j] = il;
    F(i, 1, k) f[a[i]][MASK(i - 1)] = 0;
}

void dijk(int A) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    F(i, 1, n) {
        if(f[i][A] < il) pq.emplace(f[i][A], i);
    }
    while(!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if(d > f[u][A]) continue;
        for(auto [v, w] : adj[u]) {
            if(f[v][A] > f[u][A] + w) {
                f[v][A] = f[u][A] + w;
                pq.emplace(f[v][A], v);
            }
        }
    }
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    prep();

    F(A, 1, MASK(k) - 1) {
        for(int B = (A - 1) & A; B; B = (B - 1) % A) {
            F(i, 1, n) {
                f[i][A] = min(f[i][A], f[i][B] + f[i][A ^ B]);
            }
        }
        dijk(A);
    }
    
    F(i, 1, n) {
        res = min(res, f[i][MASK(k) - 1]);
    }

    cout << res;


    return 0;
}

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