Submission #452091

#	Time	Username	Problem	Language	Result	Execution time	Memory
452091		couplefire	Cities (BOI16_cities)	C++17	100 / 100	2489 ms	47836 KiB

cities

#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 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 26 / 26