Submission #1241949

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241949		CrabCNH	Cities (BOI16_cities)	C++20	0 / 100	2549 ms	52984 KiB

cities

#include <bits/stdc++.h>

#define int long long
#define pii pair <int, int>

using namespace std;

const int maxN = 2e5 + 5;
const int inf = 1e18 + 7;

vector <pii> adj[maxN];
int n, k, m;
int L[maxN][(1 << 5) + 1];
int spe[6];
int mp[maxN];

struct Node {
    int dis, node, mask;
};

struct cmp {
    bool operator () (Node A, Node B) {
        return A.dis > B.dis;
    }
};

bool bit (int x, int i) {
    return ((x >> i) & 1);
}

int onBit (int x, int i) {
    return (x | (1 << i));
}

void dijkstra (int st) {
    priority_queue <Node, vector <Node>, cmp> pq;
    for (int i = 1; i <= n; i ++) {
        for (int mask = 0; mask < (1 << k); mask ++) {
            L[i][mask] = inf;
        }
    }
    L[st][onBit (0, 0)] = 0;
    pq.push ({L[st][onBit (0, 0)], st, onBit (0, 0)});
    while (!pq.empty ()) {
        auto [c, u, mask] = pq.top ();
        pq.pop ();
        //cout << c << ' ' << u << ' ' << mask << '\n';
        if (c > L[u][mask]) {
            continue;
        }
        for (auto [v, w] : adj[u]) {
            if (mp[v] != 0) {
                int nxtMask = onBit (mask, mp[v] - 1);
                if (L[v][nxtMask] > L[u][mask] + w) {
                    L[v][nxtMask] = L[u][mask] + w;
                    pq.push ({L[v][nxtMask], v, nxtMask});
                }
            }
            else {
                if (L[v][mask] > L[u][mask] + w) {
                    L[v][mask] = L[u][mask] + w;
                    pq.push ({L[v][mask], v, mask});
                }
            }
        }
    }
}

signed main () {
    ios_base :: sync_with_stdio (0);
    cin.tie (0);
    cin >> n >> k >> m;
    vector <int> all;
    for (int i = 1; i <= k; i ++) {
        cin >> spe[i];
        all.push_back (spe[i]);
        mp[spe[i]] = i;
    }
    for (int i = 1; i <= m; i ++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back ({v, w});
        adj[v].push_back ({u, w});
    }
    int res = inf;
    for (int i = 1; i <= k; i ++) {
        dijkstra (spe[i]);
        for (auto u : all) {
            for (int mask = 0; mask < (1 << k); mask ++) {
                int t = 0;
                for (int c = 0; c < k; c ++) {
                    t += bit (mask, c);
                }
                if (t == k) {
                    res = min (res, L[u][mask]);
                }
            }
        }
    }
    cout << res;
}

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