Submission #925632

#	Time	Username	Problem	Language	Result	Execution time	Memory
925632		irmuun	Cities (BOI16_cities)	C++17	36 / 100	408 ms	23728 KiB

cities

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

struct dsu{
    vector<ll>p,sz;
    dsu(ll n){
        p.resize(n+1);
        iota(p.begin(),p.end(),0);
        sz.resize(n+1);
        fill(sz.begin(),sz.end(),1);
    }
    ll find(ll x){
        if(p[x]==x){
            return x;
        }
        return p[x]=find(p[x]);
    }
    bool same(ll x,ll y){
        x=find(x);
        y=find(y);
        if(x==y){
            return true;
        }
        else{
            return false;
        }
    }
    void merge(ll x,ll y){
        x=find(x);
        y=find(y);
        if(x!=y){
            if(sz[x]<sz[y]){
                swap(x,y);
            }
            sz[x]+=sz[y];
            p[y]=x;
        }
    }
};

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n,k,m;
    cin>>n>>k>>m;
    ll dist[n+5],p[k+5];
    for(ll i=1;i<=k;i++){
        cin>>p[i];
        p[i]--;
    }
    vector<pair<ll,ll>>adj[n+5];
    vector<array<ll,3>>edge;
    for(ll i=1;i<=m;i++){
        ll a,b,c;
        cin>>a>>b>>c;
        a--,b--;
        edge.pb({c,a,b});
        adj[a].pb({b,c});
        adj[b].pb({a,c});
    }
    sort(all(edge));
    if(n<=20){
        ll ans=1e18;
        vector<bool>used(n);
        for(ll i=1;i<(1<<n);i++){
            fill(all(used),0);
            for(ll j=0;j<n;j++){
                if(i&(1<<j)){
                    used[j]=true;
                }
            }
            bool ok=true;
            for(ll j=1;j<=k;j++){
                if(used[p[j]]==false){
                    ok=false;
                    break;
                }
            }
            if(!ok) continue;
            dsu ds(n);
            ll cost=0;
            for(auto [c,a,b]:edge){
                if(used[a]==false||used[b]==false) continue;
                if(ds.same(a,b)==false){
                    ds.merge(a,b);
                    cost+=c;
                }
            }
            for(ll j=2;j<=k;j++){
                if(ds.same(p[j-1],p[j])==false){
                    ok=false;
                }
            }
            if(ok){
                ans=min(ans,cost);
            }
        }
        cout<<ans;
        return 0;
    }
    vector<ll>tot(n+5,0);
    for(ll i=1;i<=k;i++){
        vector<ll>dist(n+5,1e18);
        set<pair<ll,ll>>st;
        st.insert({0,p[i]});
        dist[p[i]]=0;
        while(!st.empty()){
            auto [d,j]=*st.begin();
            st.erase(st.begin());
            for(auto [b,c]:adj[j]){
                if(dist[j]+c<dist[b]){
                    if(dist[b]<1e18){
                        st.erase({dist[b],b});
                    }
                    dist[b]=dist[j]+c;
                    st.insert({dist[b],b});
                }
            }
        }
        for(ll j=1;j<=n;j++){
            tot[j]+=dist[j];
        }
    }
    ll ans=1e18;
    for(ll i=1;i<=n;i++){
        ans=min(ans,tot[i]);
    }
    cout<<ans;
}

Compilation message (stderr)

cities.cpp: In function 'int main()':
cities.cpp:53:8: warning: unused variable 'dist' [-Wunused-variable]
   53 |     ll dist[n+5],p[k+5];
      |        ^~~~

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