Submission #1182990

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182990		ZeroCool	Cities (BOI16_cities)	C++20	100 / 100	1453 ms	40780 KiB

cities

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

#pragma GCC optimize("unroll-loops,O3,Ofast")

//#define int long long
#define ll long long
#define ld long double
#define ar array
#define all(v) v.begin(), v.end()

using namespace std;



const int N = 1e6 + 20;
const int LOG = 20;
const ll INF = 1e16;
const int MOD = 1e9 + 7;

template<typename T>
void chmin(T &x,T y){x = min(x, y);};
template<typename T>
void chmax(T &x,T y){x = max(x, y);};
void mm(int &x){x = (x % MOD + MOD) % MOD;};

ld dst(int x1, int y1,int x2,int y2){
    int x = x1 - y1;
    int y = x2 - y2;
    return sqrt(x * x + y * y);
}


signed main(){ios_base::sync_with_stdio(false);cin.tie(0);
    int n, k, m;
    cin>>n>>k>>m;
    int A[k];
    for(int i = 0;i < k;i++)cin>>A[i], --A[i];
    vector<ar<int,2>> g[n];
    while(m--){
        int a, b, c;
        cin>>a>>b>>c;
        --a, --b;
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }
   // assert(0);
    ll dp[(1 << k)][n];
    for(int i = 0;i < n;i++){
        for(int j = 0;j < (1 << k);j++)dp[j][i] = INF;
    }
    bool vis[n];
    for(int i = 0;i < k;i++)dp[(1 << i)][A[i]] = 0;
    for(int msk = 1;msk < (1 << k);msk++){
        for(int msk1 = msk;msk1;msk1 = (msk1 - 1) & msk){
            int msk2 = msk ^ msk1;
            for(int i = 0;i < n;i++)chmin(dp[msk][i], dp[msk1][i] + dp[msk2][i]);
        }
        priority_queue<ar<ll,2> > pq;
        memset(vis, 0, sizeof vis);
        for(int i = 0;i < n;i++){
            if(dp[msk][i] < INF)pq.push({-dp[msk][i], i});
        }
        while(pq.size()){
            auto [d, x] = pq.top();
            pq.pop();
            if(vis[x])continue;
            vis[x] = 1;
            //cout<<msk<<" "<<x<<": "<<-d<<endl;
            for(auto [u, w] : g[x]){
                if(dp[msk][x] + w < dp[msk][u]){
                    dp[msk][u] = dp[msk][x] + w;
                    pq.push({-dp[msk][u], u});
                }
            }
        }
    }
    ll ans = INF;
    for(int i = 0;i < n;i++)chmin(ans, dp[(1 << k) - 1][i]);
    cout<<ans;
}

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