Submission #548116

#	Time	Username	Problem	Language	Result	Execution time	Memory
548116		zxcvbnm	Cities (BOI16_cities)	C++14	100 / 100	2491 ms	49848 KiB

cities

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

constexpr int nax = 1e5 + 5;
constexpr int kax = 33;
constexpr ll INF = 1e15 + 5;


vector<pli> adj[nax];
ll dp[nax][kax];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k, m;
    cin >> n >> k >> m;

    vector<int> a(k);
    for(int& i : a) {
        cin >> i;
        i--;
    }

    for(int i = 0; i < m; i++) {
        int x, y, w;
        cin >> x >> y >> w;
        x--, y--;
        adj[x].push_back({w, y});
        adj[y].push_back({w, x});
    }


    for(int i = 0; i < nax; i++) {
        for(int j = 0; j < kax; j++) {
            dp[i][j] = INF;
        }
    }

    for(int i = 0; i < k; i++) {
        dp[a[i]][1<<i] = 0;
    }

    vector<pair<int, int>> poss[kax];
    for(int i = 0; i < kax; i++) {
        for(int j = i; j < kax; j++) {
            if ((i|j) >= kax) continue;
            poss[(i|j)].push_back({i, j});
        }
    }

    for(int mask = 0; mask < (1<<k); mask++) {
        for(int root = 0; root < n; root++) {
            for(const auto& i : poss[mask]) {
                dp[root][mask] = min(dp[root][mask], dp[root][i.first] + dp[root][i.second]);
            }
        }

        priority_queue<pli, vector<pli>, greater<pli>> q;
        for(int root = 0; root < n; root++) {
            if (dp[root][mask] != INF) {
                q.emplace(dp[root][mask], root);
            }
        }

        bool vis[nax];
        memset(vis, false, sizeof vis);

        while(!q.empty()) {
            auto v = q.top();
            q.pop();

            if (vis[v.second]) continue;

            vis[v.second] = true;

            if (dp[v.second][mask] != v.first) continue;

            for(const auto& u : adj[v.second]) {
                ll dist = v.first + u.first;
                if (dist < dp[u.second][mask]) {
                    dp[u.second][mask] = dist;
                    q.emplace(dp[u.second][mask], u.second);
                }
            }
        }
    }

    ll ans = INF;
    for(int i = 0; i < n; i++) {
        ans = min(ans, dp[i][(1<<k)-1]);
    }

    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