Submission #1280927

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280927		thegodbridgexd	Cities (BOI16_cities)	C++20	100 / 100	1572 ms	44628 KiB

cities

//pragma GCC optimize("Ohio")
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define matrix vector<vector<ll>>
#define fi first
#define se second
#define BIG __int128
#define wtf pair<ll,ll>
#define db long double
//MAIN
const int N = 1e5, K = 5, MASK = (1 << K) - 1;
int n, k, m, limit, a[K + 1];
ll dp[MASK + 1][N + 1];
vector<wtf> con[N + 1];
void mini(ll& a, ll b){
    a = min(a, b);
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    /*
    freopen("cquery.inp", "r", stdin);
    freopen("cquery.out", "w", stdout);
    //*/
    cin >> n >> k >> m; limit = (1 << k) - 1;
    for (int i = 1; i <= k; i++) cin >> a[i];
    for (int i = 1; i <= m; i++){
        int u, v, w; cin >> u >> v >> w;
        con[u].push_back({v, w});
        con[v].push_back({u, w});
    }   
    for (int mask = 0; mask <= limit; mask++) for (int i = 1; i <= n; i++) dp[mask][i] = LLONG_MAX;
    for (int i = 1; i <= k; i++) dp[1 << (i - 1)][a[i]] = 0;
    for (int i = 1; i <= n; i++) dp[0][i] = 0;
    for (int mask = 1; mask <= limit; mask++){
        for (int smask = mask; ; smask = (smask - 1) & mask){
            for (int i = 1; i <= n; i++){
                int omask = mask ^ smask;
                if (dp[smask][i] != LLONG_MAX && dp[omask][i] != LLONG_MAX){
                    mini(dp[mask][i], dp[smask][i] + dp[omask][i]);
                }
            }
            if (smask == 0) break;
        }
        
        priority_queue<wtf, vector<wtf>, greater<wtf>> pq;
        for (int i = 1; i <= n; i++) if (dp[mask][i] != LLONG_MAX) pq.push({dp[mask][i], i});
        while (!pq.empty()){
            auto [val, u] = pq.top(); pq.pop();
            //if (val > dp[mask][u]) continue;
            for (auto [v, w] : con[u]){
                ll newval = val + w;
                if (dp[mask][v] > newval){
                    dp[mask][v] = newval;
                    pq.push({newval, v});
                }
            }
        }
    }
    ll kq = LLONG_MAX;
    for (int i = 1; i <= n; i++) kq = min(kq, dp[limit][i]);
    cout << kq;
}

• Subtask 1: 22 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 26 / 26