oj.uz

Submission #548116

# Submission time Handle Problem Language Result Execution time Memory
548116 2022-04-12T13:15:22 Z zxcvbnm Cities (BOI16_cities) C++14
100 / 100
 2491 ms 49848 KB 
#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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28500 KB Output is correct
2 Correct 14 ms 28500 KB Output is correct
3 Correct 13 ms 28500 KB Output is correct
4 Correct 13 ms 28500 KB Output is correct
5 Correct 14 ms 28480 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 612 ms 49572 KB Output is correct
2 Correct 607 ms 49048 KB Output is correct
3 Correct 408 ms 39696 KB Output is correct
4 Correct 95 ms 41228 KB Output is correct
5 Correct 307 ms 47452 KB Output is correct
6 Correct 80 ms 41044 KB Output is correct
7 Correct 16 ms 28752 KB Output is correct
8 Correct 15 ms 28764 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 28772 KB Output is correct
2 Correct 19 ms 28756 KB Output is correct
3 Correct 15 ms 28628 KB Output is correct
4 Correct 16 ms 28688 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1179 ms 49588 KB Output is correct
2 Correct 1204 ms 49080 KB Output is correct
3 Correct 788 ms 39768 KB Output is correct
4 Correct 708 ms 47080 KB Output is correct
5 Correct 175 ms 42224 KB Output is correct
6 Correct 86 ms 43156 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2485 ms 49736 KB Output is correct
2 Correct 2491 ms 49848 KB Output is correct
3 Correct 2450 ms 49136 KB Output is correct
4 Correct 1684 ms 39584 KB Output is correct
5 Correct 1293 ms 46764 KB Output is correct
6 Correct 321 ms 42328 KB Output is correct
7 Correct 93 ms 43468 KB Output is correct