Submission #1178373

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178373		ezzzay	Cities (BOI16_cities)	C++20	100 / 100	1248 ms	72004 KiB

cities

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define pb push_back
const int N=2e5+5;
vector<pair<int,int>>v[N];
int dp[33][N];
int n,m,k;
void find(int x, int P){
    for(int i=1;i<=n;i++){
        dp[P][i]=1e15;
    }
    dp[P][x]=0;
    
}
signed main(){
    cin>>n>>k>>m;
    vector<int>vc;
    for(int i=1;i<=k;i++){
        int a;
        cin>>a;
        vc.pb(a);
    }
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        v[a].pb({b,c});
        v[b].pb({a,c});
    }
    for(int i=0;i<N;i++){
        for(int j=0;j<(1<<k);j++){
            dp[j][i]=1e15;
        }
    }
    for(int i=0;i<k;i++){
        dp[1<<i][vc[i]]=0;
    }
    for(int msk=0;msk<(1<<k);msk++){
        for(int x=0;x<msk;x++){
            if((msk|x)!=msk)continue;
            int y=msk ^x;
            for(int i=1;i<=n;i++){
                dp[msk][i]=min(dp[msk][i],dp[x][i]+dp[y][i]);
            }
        }
        priority_queue<pair<int,int>>q;
        for(int i=1;i<=n;i++){
            if(dp[msk][i]<1e15){
                q.push({-dp[msk][i],i});
            }
        }
        while(!q.empty()){
            int w=-q.top().ff;
            int a=q.top().ss;
            q.pop();
            if(dp[msk][a]<w)continue;
            for(auto p:v[a]){
                int b=p.ff;
                int c=p.ss;
                if(dp[msk][b]>dp[msk][a]+c){
                    dp[msk][b]=dp[msk][a]+c;
                    q.push({-dp[msk][b],b});
                }
            }
        }
    }
    int ans=1e15;
    for(int i=0;i<k;i++){
        ans=min(ans,dp[(1<<k)-1][vc[i]]);
    }
    cout<<ans;
}

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