Submission #485523

#	Time	Username	Problem	Language	Result	Execution time	Memory
485523		phamhoanghiep	Cities (BOI16_cities)	C++14	100 / 100	2451 ms	44828 KiB

cities

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> ii;
const int maxn=1e5+5;
const int inf=1e15;
int dp[1<<5][maxn];
vector<ii> AdjList[maxn];
int sp[maxn];
int rsp[maxn];
int n,m,k;
void dijkstra(int mask) {
    //cout<<"dijk "<<mask<<endl;
    priority_queue<ii,vector<ii>,greater<ii>> pq;
    for(int i=1 ; i<=n ; i++) {
        pq.push(ii(dp[mask][i],i));
        //cout<<"dp "<<mask<<" "<<i<<" = "<<dp[mask][i]<<endl;
    }
    while(!pq.empty()) {
        ii tmp=pq.top();
        pq.pop();
        int val=tmp.first;
        int node=tmp.second;
        //cout<<"val node "<<val<<" "<<node<<endl;
        if(dp[mask][node]>val) continue;
        //cout<<"dp "<<mask<<" "<<node<<" = "<<dp[mask][node]<<endl;
        //cout<<"val node "<<val<<" "<<node<<endl;
        for(ii tmp: AdjList[node]) {
            int u=tmp.first;
            int w=tmp.second;
            if(dp[mask][u]>dp[mask][node]+w) {
                dp[mask][u]=dp[mask][node]+w;
                pq.push(ii(dp[mask][u],u));
            }
        }
    }
}
signed main() {
    cin>>n>>k>>m;
    for(int i=0 ; i<k ; i++) {
        cin>>sp[i];
        rsp[sp[i]]=i+1;
    }
    for(int i=1 ; i<=m ; i++) {
        int u,v,w;
        cin>>u>>v>>w;
        AdjList[u].push_back(ii(v,w));
        AdjList[v].push_back(ii(u,w));
    }
    for(int i=0 ; i<(1<<k) ; i++) {
        for(int j=1 ; j<=n ; j++) {
            dp[i][j]=inf;
        }
    }
    for(int i=0 ; i<k ; i++) {
        dp[(1<<i)][sp[i]]=0;
        //cout<<"dp "<<(1<<i)<<" "<<sp[i]<<endl;
    }
    for(int i=1 ; i<=n ; i++) dp[0][i]=0;
    for(int mask=0 ; mask<(1<<k) ; mask++) {
        for(int i=1 ; i<=n ; i++) {
            //cout<<dp[mask][i]<<" ";
        }
        //cout<<endl;
    }
    for(int mask=1 ; mask<(1<<k) ; mask++) {
        //cout<<"mask = "<<mask<<endl;
        for(int mask2=mask ; mask2>0 ; mask2=(mask2-1)&mask) {
            int rmask=mask^mask2;
            //cout<<"mask2 rmask "<<mask2<<" "<<rmask<<endl;
            for(int i=1 ; i<=n ; i++) {
                if(!rsp[i]) dp[mask][i]=min(dp[mask][i],dp[mask2][i]+dp[rmask][i]);
                else dp[mask][i]=min(dp[mask][i],dp[mask2][i]+dp[rmask^(1<<(rsp[i]-1))][i]);
            }
        }
        dijkstra(mask);
    }
    int ans=inf;
    int full=(1<<k)-1;
    for(int i=1 ; i<=n ; i++) ans=min(ans,dp[full][i]);
    cout<<ans;
}

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