oj.uz

Submission #452091

# Submission time Handle Problem Language Result Execution time Memory
452091 2021-08-03T18:46:52 Z couplefire Cities (BOI16_cities) C++17
100 / 100
 2489 ms 47836 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 100005;
const int INF = 0x3f3f3f3f3f3f3f3f;

int n, k, m, pts[5], dp[32][N], ans = INF;
vector<array<int, 2>> adj[N];

signed main(){
    // freopen("a.in", "r", stdin);
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> k >> m;
    for(int i = 0; i<k; ++i)
        cin >> pts[i], --pts[i];
    for(int i = 0; i<m; ++i){
        int a, b, c;
        cin >> a >> b >> c; --a; --b;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }
    for(int i = 0; i<k; ++i){
        memset(dp[1<<i], 63, sizeof dp[1<<i]);
        priority_queue<array<int, 2>, vector<array<int, 2>>, greater<>> pq;
        dp[1<<i][pts[i]] = 0; pq.push({0, pts[i]});
        while(!pq.empty()){
            auto [d, v] = pq.top(); pq.pop();
            if(d != dp[1<<i][v]) continue;
            for(auto [u, w] : adj[v])
                if(dp[1<<i][u] > d+w)
                    dp[1<<i][u] = d+w, pq.push({d+w, u});
        }
    }
    for(int mask = 1; mask<(1<<k); ++mask){
        if(__builtin_popcountll(mask)<=1) continue;
        memset(dp[mask], 63, sizeof dp[mask]);
        priority_queue<array<int, 2>, vector<array<int, 2>>, greater<>> pq;
        for(int i = 0; i<n; ++i){
            int tmp = INF;
            for(int smask = (mask-1)&mask; smask; smask = (smask-1)&mask)
                tmp = min(tmp, dp[smask][i]+dp[mask^smask][i]);
            dp[mask][i] = tmp; pq.push({tmp, i});
        }
        while(!pq.empty()){
            auto [d, v] = pq.top(); pq.pop();
            if(d != dp[mask][v]) continue;
            for(auto [u, w] : adj[v])
                if(dp[mask][u] > d+w)
                    dp[mask][u] = d+w, pq.push({d+w, u});
        }
    }
    for(int i = 0; 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 4 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 5 ms 8140 KB Output is correct
4 Correct 9 ms 14412 KB Output is correct
5 Correct 14 ms 26880 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 615 ms 29108 KB Output is correct
2 Correct 547 ms 28472 KB Output is correct
3 Correct 335 ms 19156 KB Output is correct
4 Correct 85 ms 20552 KB Output is correct
5 Correct 307 ms 23752 KB Output is correct
6 Correct 80 ms 17304 KB Output is correct
7 Correct 7 ms 8396 KB Output is correct
8 Correct 5 ms 5196 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14540 KB Output is correct
2 Correct 12 ms 14540 KB Output is correct
3 Correct 11 ms 14460 KB Output is correct
4 Correct 10 ms 14540 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1208 ms 35212 KB Output is correct
2 Correct 1143 ms 34724 KB Output is correct
3 Correct 753 ms 25288 KB Output is correct
4 Correct 642 ms 32528 KB Output is correct
5 Correct 189 ms 27860 KB Output is correct
6 Correct 98 ms 28984 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2489 ms 47836 KB Output is correct
2 Correct 2397 ms 47656 KB Output is correct
3 Correct 2286 ms 47308 KB Output is correct
4 Correct 1629 ms 37988 KB Output is correct
5 Correct 1266 ms 44928 KB Output is correct
6 Correct 301 ms 40716 KB Output is correct
7 Correct 112 ms 41776 KB Output is correct