Submission #1178361

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178361		ezzzay	Cities (BOI16_cities)	C++20	0 / 100	241 ms	21064 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 dist[5][N];
int n,m,k;
void find(int x, int P){
    for(int i=1;i<=n;i++){
        dist[P][i]=1e15;
    }
    dist[P][x]=0;
    priority_queue<pair<int,int>>q;
    q.push({0,x});
    while(!q.empty()){
        int w=-q.top().ff;
        int a=q.top().ss;
        q.pop();
        if(dist[P][a]<w)continue;
        for(auto p:v[a]){
            int b=p.ff;
            int c=p.ss;
            if(dist[P][b]>dist[P][a]+c){
                dist[P][b]=dist[P][a]+c;
                q.push({-dist[P][b],b});
            }
        }
    }
}
int dp[100];
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<k;i++){
        find(vc[i],i);
    }
    for(int i=0;i<100;i++)dp[i]=1e15;
    for(int i=0;i<k;i++){
        dp[(1<<i)]=0;
    }
    for(int i=1;i<(1<<k);i++){
        vector<int>A,B;
        for(int j=0;j<k;j++){
            if(i&(1<<j))A.pb(j);
            else B.pb(j);
        }
        for(auto b:B){
            for(auto a:A){
                dp[i+(1<<b)]=min(dp[i+(1<<b)],dp[i]+dist[a][vc[b]]);
            }
        }
    }
    cout<<dp[(1<<k)-1];
}

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