Submission #1157245

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157245		Hamed_Ghaffari	Cities (BOI16_cities)	C++20	100 / 100	592 ms	24764 KiB

cities

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#define X first
#define Y second
#define maxs(a,b) (a=max(a,b))
#define mins(a,b) (a=min(a,b))
#define lc id<<1
#define rc lc|1
#define mid ((l+r)>>1)
#define pb push_back

const int MXN = 1e5+5;
const int MXK = 4;

int n, k, m, V[MXK], root;
vector<pii> g[MXN];
ll dp[1<<MXK][MXN];
priority_queue<pll> pq;

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> k >> m >> root; k--;
    for(int i=0; i<k; i++) cin >> V[i];
    for(int i=0,u,v,w; i<m; i++) {
        cin >> u >> v >> w;
        g[u].pb(pii(v,w));
        g[v].pb(pii(u,w));
    }
    for(int msk=1; msk<(1<<k); msk++)
        fill(dp[msk]+1, dp[msk]+n+1, 2e18);
    for(int msk=0; msk<(1<<k); msk++) {
        for(int v=1; v<=n; v++) {
            for(int smsk=(msk-1)&msk; smsk; smsk=(smsk-1)&msk)
                mins(dp[msk][v], dp[smsk][v]+dp[msk^smsk][v]);
            pq.push(pll(-dp[msk][v], v));
        }
        while(!pq.empty()) {
            ll d = -pq.top().X;
            int v = pq.top().Y;
            pq.pop();
            if(d!=dp[msk][v]) continue;
            for(auto [u, w] : g[v])
                if(dp[msk][u]>d+w)
                    pq.push(pll(-(dp[msk][u]=d+w), u));
        }
        for(int i=0; i<k; i++)
            mins(dp[msk|(1<<i)][V[i]], dp[msk][V[i]]);
    }
    cout << dp[(1<<k)-1][root] << '\n';
    return 0;
}

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