Submission #529991

#	Time	Username	Problem	Language	Result	Execution time	Memory
529991		KoD	Cities (BOI16_cities)	C++17	100 / 100	1625 ms	48604 KiB

cities

#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::tuple;
using std::pair;

using ll = long long;

constexpr ll inf = std::numeric_limits<ll>::max() / 2;

template <class T> using Heap = std::priority_queue<T, vector<T>, std::greater<>>;

template <class T> bool setmin(T& x, const T& y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N, K, M;
    std::cin >> N >> K >> M;
    vector<int> V(K);
    for (auto& x : V) {
        std::cin >> x;
        x -= 1;
    }

    vector<vector<pair<int, int>>> graph(N);
    for (int i = 0; i < M; ++i) {
        int a, b, c;
        std::cin >> a >> b >> c;
        a -= 1, b -= 1;
        graph[a].emplace_back(b, c);
        graph[b].emplace_back(a, c);
    }

    vector merge(N, vector(1 << K, inf));
    for (int i = 0; i < K; ++i) {
        merge[V[i]][1 << i] = 0;
    }
    for (int set = 1; set < (1 << K); ++set) {
        for (int sub = set; (sub -= 1) &= set;) {
            for (int i = 0; i < N; ++i) {
                setmin(merge[i][set], merge[i][sub] + merge[i][set & ~sub]);
            }
        }
        if (__builtin_popcount(set) >= 3) {
            continue;
        }
        Heap<pair<ll, int>> heap;
        const auto push = [&](const int u, const ll d) {
            if (setmin(merge[u][set], d)) {
                heap.emplace(d, u);
            }
        };
        for (int i = 0; i < N; ++i) {
            if (merge[i][set] != inf) {
                heap.emplace(merge[i][set], i);
            }
        }
        while (!heap.empty()) {
            const auto [d, u] = heap.top();
            heap.pop();
            if (d > merge[u][set]) {
                continue;
            }
            for (const auto& [v, c] : graph[u]) {
                push(v, d + c);
            }
        }
    }

    ll ans = inf;
    for (int i = 0; i < N; ++i) {
        setmin(ans, merge[i][(1 << K) - 1]);
    }
    std::cout << ans << '\n';

    return 0;
}

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