oj.uz

Submission #1111247

# Submission time Handle Problem Language Result Execution time Memory
1111247 2024-11-11T20:40:56 Z f0rizen Cities (BOI16_cities) C++17
100 / 100
 1746 ms 44792 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int inf = 1e9 + 7;
const ll infll = 1e18;

template<typename T>
istream &operator>>(istream &is, vector<T> &a) {
    for (auto &i : a) {
        is >> i;
    }
    return is;
}

int32_t main() {
#ifdef LOCAL
    freopen("/tmp/input.txt", "r", stdin);
#else
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#endif
    int n, k, m;
    cin >> n >> k >> m;
    vector<int> a(k);
    cin >> a;
    for (auto &i : a) {
        --i;
    }
    vector<vector<pair<int, int>>> g(n);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        --u, --v;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    vector<vector<ll>> dp(1 << k, vector<ll>(n, infll));
    for (int i = 0; i < k; ++i) {
        dp[1 << i][a[i]] = 0;
    }
    for (int mask = 0; mask < (1 << k); ++mask) {
        for (int s = mask; s > 0; s = (s - 1) & mask) {
            for (int i = 0; i < n; ++i) {
                dp[mask][i] = min(dp[mask][i], dp[s][i] + dp[mask ^ s][i]);
            }
        }
        using pii = pair<ll, int>;
        priority_queue<pii, vector<pii>, greater<pii>> pq;
        for (int i = 0; i < n; ++i) {
            if (dp[mask][i] < infll) {
                pq.push({dp[mask][i], i});
            }
        }
        while (!pq.empty()) {
            auto [_, v] = pq.top();
            pq.pop();
            if (_ > dp[mask][v]) {
                continue;
            }
            for (auto [u, w] : g[v]) {
                if (dp[mask][u] > dp[mask][v] + w) {
                    dp[mask][u] = dp[mask][v] + w;
                    pq.push({dp[mask][u], u});
                }
            }
        }
    }
    ll ans = infll;
    for (int i = 0; i < n; ++i) {
        ans = min(ans, dp[(1 << k) - 1][i]);
    }
    cout << ans << "\n";
    return 0;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 412 ms 21788 KB Output is correct
2 Correct 382 ms 23860 KB Output is correct
3 Correct 184 ms 15832 KB Output is correct
4 Correct 64 ms 8628 KB Output is correct
5 Correct 208 ms 16168 KB Output is correct
6 Correct 43 ms 5116 KB Output is correct
7 Correct 3 ms 592 KB Output is correct
8 Correct 2 ms 592 KB Output is correct

Subtask #3
15.0 / 15.0

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

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 838 ms 28044 KB Output is correct
2 Correct 827 ms 29264 KB Output is correct
3 Correct 440 ms 22104 KB Output is correct
4 Correct 483 ms 17152 KB Output is correct
5 Correct 128 ms 8916 KB Output is correct
6 Correct 48 ms 6628 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1746 ms 40800 KB Output is correct
2 Correct 1631 ms 44792 KB Output is correct
3 Correct 1426 ms 44672 KB Output is correct
4 Correct 919 ms 36812 KB Output is correct
5 Correct 782 ms 27540 KB Output is correct
6 Correct 185 ms 12744 KB Output is correct
7 Correct 61 ms 10316 KB Output is correct