oj.uz

Submission #1106143

# Submission time Handle Problem Language Result Execution time Memory
1106143 2024-10-29T11:16:43 Z votranngocvy Cities (BOI16_cities) C++14
100 / 100
 1411 ms 51456 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair<int,int>
#define fi first
#define se second
const int N = 1e5 + 5;
const int inf = 0x3f3f3f3f3f3f3f3f;
const int M = (1 << 5) + 5;
int a[10],dp[M][N];
vector<pii>g[N];

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n,k,m;
    cin >> n >> k >> m;
    for (int i = 0; i < k; i++) cin >> a[i];
    for (int i = 1; i <= m; i++) {
        int u,v,w;
        cin >> u >> v >> w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    for (int mask = 0; mask < (1 << k); mask++)
        for (int i = 1; i <= n; i++) dp[mask][i] = inf;
    for (int i = 0; i < k; i++) dp[(1 << i)][a[i]] = 0;
    for (int mask = 1; mask < (1 << k); mask++) {
        for (int sub = mask & (mask - 1); sub > 0; sub = mask & (sub - 1)) 
            for (int i = 1; i <= n; i++)
                dp[mask][i] = min(dp[mask][i],dp[sub][i] + dp[mask ^ sub][i]);
        priority_queue<pii,vector<pii>,greater<pii>>q;
        for (int i = 1; i <= n; i++)
            if (dp[mask][i] < inf) q.push({dp[mask][i],i});
        while (!q.empty()) {
            int u = q.top().se,c = q.top().fi;
            q.pop();
            if (dp[mask][u] != c) continue;
            for (auto x: g[u]) {
                int v = x.fi,w = x.se;
                if (dp[mask][v] > dp[mask][u] + w) {
                    dp[mask][v] = dp[mask][u] + w;
                    q.push({dp[mask][v],v});
                }
            }
        }
    }
    int ans = inf;
    for (int i = 1; i <= n; i++) ans = min(ans,dp[(1 << k) - 1][i]);
    cout << ans << "\n";
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6736 KB Output is correct
2 Correct 2 ms 6736 KB Output is correct
3 Correct 2 ms 8784 KB Output is correct
4 Correct 3 ms 14928 KB Output is correct
5 Correct 4 ms 27216 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 32812 KB Output is correct
2 Correct 312 ms 32696 KB Output is correct
3 Correct 168 ms 21876 KB Output is correct
4 Correct 52 ms 21320 KB Output is correct
5 Correct 175 ms 27652 KB Output is correct
6 Correct 47 ms 19096 KB Output is correct
7 Correct 4 ms 9040 KB Output is correct
8 Correct 3 ms 6992 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15184 KB Output is correct
2 Correct 6 ms 15200 KB Output is correct
3 Correct 5 ms 14928 KB Output is correct
4 Correct 5 ms 15000 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 741 ms 38148 KB Output is correct
2 Correct 703 ms 38760 KB Output is correct
3 Correct 379 ms 28600 KB Output is correct
4 Correct 422 ms 33768 KB Output is correct
5 Correct 120 ms 28496 KB Output is correct
6 Correct 57 ms 29772 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1411 ms 51032 KB Output is correct
2 Correct 1352 ms 51456 KB Output is correct
3 Correct 1305 ms 51172 KB Output is correct
4 Correct 945 ms 40356 KB Output is correct
5 Correct 751 ms 48448 KB Output is correct
6 Correct 200 ms 41032 KB Output is correct
7 Correct 64 ms 42068 KB Output is correct