제출 #1242223

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1242223		CrabCNH	Cities (BOI16_cities)	C++20	100 / 100	1244 ms	47724 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];

struct Node {
    int dis, node;
};

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 () {
    for (int i = 1; i <= n; i ++) {
        for (int mask = 0; mask < (1 << k); mask ++) {
            L[i][mask] = inf;
        }
    }
    for (int i = 1; i <= k; i ++) {
        L[spe[i]][onBit (0, i - 1)] = 0;
    }
    for (int mask = 0; mask < (1 << k); mask ++) {
        for (int i = 1; i <= n; i ++) {
            for (int s = (mask - 1) & mask; s > 0; s = ((s - 1) & mask)) {
                L[i][mask] = min (L[i][mask], L[i][s] + L[i][mask ^ s]);
            }
        }
        priority_queue <Node, vector <Node>, cmp> pq;
        for (int i = 1; i <= n; i ++) {
            if (L[i][mask] != inf) {
                pq.push ({L[i][mask], i});
            }
        }
        while (!pq.empty ()) {
            auto [c, u] = pq.top ();
            //cout << c << ' ' << u << '\n';
            pq.pop ();
            if (c > L[u][mask]) {
                continue;
            }
            for (auto [v, w] : adj[u]) {
                if (L[v][mask] > L[u][mask] + w) {
                    L[v][mask] = L[u][mask] + w;
                    pq.push ({L[v][mask], v});
                }
            }
        }
    }
}

signed main () {
    ios_base :: sync_with_stdio (0);
    cin.tie (0);
    cin >> n >> k >> m;
    for (int i = 1; i <= k; i ++) {
        cin >> spe[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;
    dijkstra ();
    for (int i = 1; i <= n; i ++) {
        res = min (res, L[i][(1 << k) - 1]);
    }
    cout << res;
}

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