Submission #1306158

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306158		satoulogarit	Cities (BOI16_cities)	C++20	100 / 100	1736 ms	41456 KiB

cities

//LongvnXD
#include <bits/stdc++.h>

#define ll long long
#define pll pair<ll, ll>
#define ii pair<int, int>
#define iii pair<ii, int>
#define dl pair<ll, ii>
#define fi first
#define se second
#define all(v) v.begin(), v.end()

const int N = 2e5 + 5;
const ll oo = 1e18 + 18;

using namespace std; 

int n, k, m, a[N], x[10];
vector<ii> g[N];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    // freopen("CAU4.inp", "r", stdin);
    // freopen("CAU4.out", "w", stdout);
    
    cin >> n >> k >> m;
    vector<ll> dist(n+1, oo);
    vector<vector<ll>> d(1 << k, vector<ll>(n+1, oo));
    
    for(int i=0; i<k; ++i) {
        cin >> x[i];
        a[x[i]] = (1 << i);
        d[a[x[i]]][x[i]] = 0;
    }
    for(int i=1, u, v, w; i<=m; ++i) {
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    
    int full = (1 << k) - 1;
    for(int mask=1; mask <= full; ++mask) {
        for(int mask1 = (mask - 1) & mask; mask1; mask1 = (mask1 - 1) & mask) {
            int mask2 = mask ^ mask1;
            for(int u=1; u<=n; ++u) {
                if(d[mask2][u] == oo || d[mask1][u] == oo) continue;
                
                d[mask][u] = min(d[mask][u], d[mask1][u] + d[mask2][u]);
            }
        }
        
        priority_queue<pll, vector<pll>, greater<pll>> q;
        for(int i=1; i<=n; ++i) dist[i] = oo;
        for(int i=1; i<=n; ++i)
            if(d[mask][i] != oo)
                dist[i] = d[mask][i], q.push({dist[i], i});

        while(q.size()) {
            pll temp = q.top(); q.pop();
            ll x = temp.fi;
            int u = temp.se;

            if(x != dist[u]) continue;

            for(ii& temp2 : g[u]) {
                int v = temp2.fi;
                int w = temp2.se;
                if(dist[v] > x + w) {
                    dist[v] = x + w;
                    q.push({x + w, v});
                }
            }
        }

        for(int i=1; i<=n; ++i)
            d[mask][i] = dist[i];
    }
    
    ll ok = oo;
    for(int i=1; i<=n; ++i)
        ok = min(ok, d[full][i]);
    cout << ok;
    
    return 0;
}

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