Submission #697925

#	Time	Username	Problem	Language	Result	Execution time	Memory
697925		FEDIKUS	Cities (BOI16_cities)	C++17	14 / 100	472 ms	21528 KiB

cities

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll maxn=2e5+10;
const ll inf=1e15;

ll n,k,m;

ll spec[10];
vector<pair<ll,ll> > g[maxn];
vector<pair<ll,pair<ll,ll> > > ng;
int vel;
ll sta1[maxn];
ll sta2[maxn];
ll d[6][maxn];
ll naj[(1<<6)];

void dijkstra(ll poc,ll* dist){
    priority_queue<pair<ll,ll> > pq;
    pq.push(pair<ll,ll>(0,poc));
    for(ll i=1;i<=n;i++) dist[i]=inf;
    dist[poc]=0;
    while(!pq.empty()){
        auto tren=pq.top();
        pq.pop();
        tren.first*=-1;
        if(dist[tren.second]<tren.first) continue;
        for(auto i:g[tren.second]){
            if(dist[i.first]>tren.first+i.second) pq.push(pair<ll,ll>(-tren.first-i.second,i.first));
            dist[i.first]=min(dist[i.first],tren.first+i.second);
        }
    }
}

ll dsu[maxn];

int root(int node){
    return dsu[node]==node ? node:dsu[node]=root(dsu[node]);
}

void join(int a,int b){
    a=root(a); b=root(b);
    dsu[a]=b;
}

ll mst(){
    for(ll i=1;i<=vel;i++) dsu[i]=i;
    sort(ng.begin(),ng.end());
    ll ret=0;
    for(auto i:ng){
        if(root(i.second.first)==root(i.second.second)) continue;
        ret+=i.first;
        join(i.second.first,i.second.second);
    }
    return ret;
}

ll dp[1<<6];

int main(){
    cin>>n>>k>>m;
    for(ll i=0;i<k;i++) cin>>spec[i];
    for(ll i=0;i<m;i++){
        ll u,v,c;
        cin>>u>>v>>c;
        g[u].push_back({v,c});
        g[v].push_back({u,c});
    }
    for(ll i=0;i<k;i++) dijkstra(spec[i],d[i]);
    for(ll mask=1;mask<(1<<k);mask++){
        naj[mask]=10*inf;
        for(ll sred=1;sred<=n;sred++){
            ll tren=0;
            for(ll node=0;node<k;node++) if(mask&(1<<node)) tren+=d[node][sred];
            naj[mask]=min(naj[mask],tren);
        }
    }
    for(ll i=0;i<k*k;i++){
        for(ll mask=1;mask<(1<<k);mask++){
            for(ll mask2=1;mask2<(1<<k);mask2++){
                if((mask&mask2)==0) continue;
                naj[mask|mask2]=min(naj[mask|mask2],naj[mask2]+naj[mask]);
            }
        }
    }
    cout<<naj[(1<<k)-1];
    return 0;
}

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