Submission #1245763

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245763		trandangquang	Cities (BOI16_cities)	C++20	100 / 100	1515 ms	40608 KiB

cities

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

#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define ii pair<int,int>
#define fi first
#define se second
#define eb emplace_back
#define ll long long

const int N=1e5+5;

int n,k,m,p[N]; ll dp[N][1<<5];
vector<ii> adj[N];

void dijkstra(int x){
    priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
    FOR(i,1,n) pq.push({dp[i][x],i});

    while(pq.size()){
        auto [du,u]=pq.top(); pq.pop();
        if(du>dp[u][x]) continue;
        for(auto [v,w]:adj[u]){
            if(dp[v][x]>dp[u][x]+w){
                dp[v][x]=dp[u][x]+w;
                pq.push({dp[v][x],v});
            }
        }
    }
}

int main(){
    cin.tie(0)->sync_with_stdio(0);

    cin>>n>>k>>m;
    FOR(i,0,k-1) cin>>p[i];
    FOR(i,1,m){
        int x,y,z; cin>>x>>y>>z;
        adj[x].eb(y,z); adj[y].eb(x,z);
    }

    memset(dp,0x3f,sizeof(dp));
    FOR(i,0,k-1) dp[p[i]][1<<i]=0;

    FOR(mask,0,(1<<k)-1){
        for(int sub=mask; sub; sub=(sub-1)&mask){
            FOR(i,1,n){
                dp[i][mask]=min(dp[i][mask],dp[i][sub]+dp[i][mask^sub]);
            }
        }
        dijkstra(mask);
    }

    ll res=1e18;
    FOR(i,1,n) res=min(res,dp[i][(1<<k)-1]);
    cout<<res<<'\n';
}

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