oj.uz

Submission #683031

# Submission time Handle Problem Language Result Execution time Memory
683031 2023-01-17T14:50:32 Z bebra Cities (BOI16_cities) C++17
100 / 100
 4368 ms 177140 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define dbg(x) cerr << #x << ": " << x << endl;


const int MAX_N = 1e5 + 5;
const int MAX_M = 2e5 + 5;
const int MAX_K = 5;
const ll INF = 1e18;
vector<pair<int, int>> g[MAX_N];
int vertices[MAX_K];
ll dist[MAX_K][MAX_N];
bool used[MAX_K][MAX_N];
ll dp[MAX_N][1 << MAX_K];
bool used_dp[MAX_N][1 << MAX_K];


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k, m;
    cin >> n >> k >> m;
    for (int i = 0; i < k; ++i) {
        cin >> vertices[i];
        --vertices[i];
    }
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        int w;
        cin >> w;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    for (int i = 0; i < k; ++i) {
        priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
        pq.emplace(0, vertices[i]);
        fill_n(dist[i], n, INF);
        dist[i][vertices[i]] = 0;
        while (!pq.empty()) {
            auto [curr_dist, v] = pq.top();
            pq.pop();
            used[i][v] = true;
            for (const auto& [u, w] : g[v]) {
                if (used[i][u]) continue;
                if (curr_dist + w >= dist[i][u]) continue;
                dist[i][u] = curr_dist + w;
                pq.emplace(dist[i][u], u);
            }
        }
    }
    ll ans = INF;
    const int max_mask = (1 << k) - 1;
    // for (int i = 0; i < k; ++i) {
    int i = 0;
        for (int j = 0; j < n; ++j) {
            for (int mask = 0; mask <= max_mask; ++mask) {
                dp[j][mask] = INF;
                used_dp[j][mask] = false;
            }
        }
        priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater<tuple<ll, int, int>>> pq;
        for (int mask = 0; mask <= max_mask; ++mask) {
            if (!(mask & (1 << i))) continue;
            dp[vertices[i]][mask] = 0;
            for (int j = 0; j < k; ++j) {
                if (mask & (1 << j)) {
                    dp[vertices[i]][mask] += dist[j][vertices[i]];
                }
            }
            pq.emplace(dp[vertices[i]][mask], vertices[i], mask);
        }
        while (!pq.empty()) {
            auto [curr_value, v, curr_mask] = pq.top();
            if (curr_mask == max_mask) {
                ans = min(ans, curr_value);
            }
            pq.pop();
            if (used_dp[v][curr_mask]) continue;
            used_dp[v][curr_mask] = true;
            for (const auto& [u, w] : g[v]) {
                for (int new_mask = curr_mask; new_mask <= max_mask; new_mask = (new_mask + 1) | curr_mask) {
                    if (used_dp[u][new_mask]) continue;
                    ll curr_cost = w;
                    for (int j = 0; j < k; ++j) {
                        if ((new_mask ^ curr_mask) & (1 << j)) {
                            curr_cost += dist[j][u];
                        }
                    }
                    if (curr_value + curr_cost >= dp[u][new_mask]) continue;
                    dp[u][new_mask] = curr_value + curr_cost;
                    pq.emplace(dp[u][new_mask], u, new_mask);
                }
            }
        }
    // }
    cout << ans << '\n';
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 738 ms 56220 KB Output is correct
2 Correct 719 ms 55836 KB Output is correct
3 Correct 343 ms 40836 KB Output is correct
4 Correct 84 ms 8180 KB Output is correct
5 Correct 343 ms 42996 KB Output is correct
6 Correct 67 ms 7872 KB Output is correct
7 Correct 4 ms 3284 KB Output is correct
8 Correct 3 ms 3028 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3412 KB Output is correct
2 Correct 10 ms 3412 KB Output is correct
3 Correct 7 ms 3412 KB Output is correct
4 Correct 7 ms 3284 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1650 ms 73604 KB Output is correct
2 Correct 1594 ms 73272 KB Output is correct
3 Correct 882 ms 54052 KB Output is correct
4 Correct 985 ms 57272 KB Output is correct
5 Correct 262 ms 18892 KB Output is correct
6 Correct 130 ms 10192 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4217 ms 172852 KB Output is correct
2 Correct 4368 ms 177140 KB Output is correct
3 Correct 3969 ms 176764 KB Output is correct
4 Correct 2262 ms 106276 KB Output is correct
5 Correct 2676 ms 94920 KB Output is correct
6 Correct 643 ms 30968 KB Output is correct
7 Correct 319 ms 14716 KB Output is correct