Submission #557099

#	Time	Username	Problem	Language	Result	Execution time	Memory
557099		OttoTheDino	Cities (BOI16_cities)	C++17	100 / 100	5059 ms	99080 KiB

cities

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

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

#define rep(i,s,e)                  for (ll i = s; i <= e; ++i)
#define rrep(i,s,e)                 for (ll i = s; i >= e; --i)
#define pb                          push_back
#define pf                          push_front
#define fi                          first
#define se                          second
#define all(a)                      a.begin(), a.end()
#define len(a)                      (ll)a.size()
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ii> vii;
typedef vector<ll> vi;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    ll n, k, m; cin >> n >> k >> m;
    
    ll T = 2;

    ll dp[T+1][n][1<<k] = {};

    vii adj[n];

    rep (i,0,n-1) rep (j,1,(1<<k)-1) dp[0][i][j] = 1e15;

    rep (i,0,k-1) {
        ll x; cin >> x;
        --x;
        dp[0][x][1<<i] = 0;
    }

    rep (i,0,m-1) {
        ll u, v, c; cin >> u >> v >> c;
        u--, v--;
        adj[u].pb({v, c});
        adj[v].pb({u, c});
    }

    rep (a,0,T-1) {

        rep (i,0,(1<<k)-1) {

            priority_queue<ii, vii, greater<ii>> pq;

            bool done[n] = {};

            rep (j,0,n-1) pq.push({dp[a][j][i], j});

            while (!pq.empty()) {
                ll u = pq.top().se, D = pq.top().fi;
                pq.pop();

                if (done[u]) continue;
                done[u] = 1;

                for (auto vc : adj[u]) {
                    if (D + vc.se < dp[a][vc.fi][i]) {
                        dp[a][vc.fi][i] = D + vc.se;
                        pq.push({dp[a][vc.fi][i], vc.fi});
                    }
                }
            }

        }

        //join together different trees
        rep (i,0,n-1) {
            rep (j,0,(1<<k)-1) dp[a+1][i][j] = dp[a][i][j];

            for (auto vc : adj[i])
                rrep (j,(1<<k)-1,0)
                    rep (b,0,(1<<k)-1)
                        if ((j&b)==b)
                            dp[a+1][i][j] = min(dp[a+1][i][j], dp[a+1][i][j^b]+vc.se+dp[a][vc.fi][b]);
        }
    }

    ll ans = LLONG_MAX;
    rep (i,0,n-1) ans = min(ans, dp[T][i][(1<<k)-1]);
    cout << ans << "\n";

    return 0;
}

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