Submission #697946

#	Time	Username	Problem	Language	Result	Execution time	Memory
697946		FEDIKUS	Cities (BOI16_cities)	C++17	100 / 100	2119 ms	51492 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[6];
vector<pair<ll,ll> > g[maxn];
ll nenaj[(1<<6)][maxn];

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);
        }
    }
}

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<(1<<k);i++) for(ll j=1;j<=n;j++) nenaj[i][j]=inf;
    for(ll i=0;i<k;i++) nenaj[1<<i][spec[i]]=0;
    for(ll mask=1;mask<(1<<k);mask++){
        ll mask1=mask;
        mask1--;
        mask1&=mask;
        while(mask1>0){
            ll mask2=mask^mask1;
            for(ll sred=1;sred<=n;sred++) nenaj[mask][sred]=min(nenaj[mask][sred],nenaj[mask1][sred]+nenaj[mask2][sred]);
            mask1--;
            mask1&=mask;
        }
        priority_queue<pair<ll,ll> > pq;
        for(ll sred=1;sred<=n;sred++) pq.push(pair<ll,ll>(-nenaj[mask][sred],sred));
        while(!pq.empty()){
            auto tren=pq.top();
            pq.pop();
            tren.first*=-1;
            if(nenaj[mask][tren.second]<tren.first) continue;
            for(auto i:g[tren.second]){
                if(nenaj[mask][i.first]>tren.first+i.second) pq.push(pair<ll,ll>(-tren.first-i.second,i.first));
                nenaj[mask][i.first]=min(nenaj[mask][i.first],tren.first+i.second);
            }
        }
    }
    cout<<*min_element(nenaj[(1<<k)-1]+1,nenaj[(1<<k)-1]+n+1);
    return 0;
}

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