Submission #537824

#	Time	Username	Problem	Language	Result	Execution time	Memory
537824		__Variatto	Cities (BOI16_cities)	C++17	100 / 100	2138 ms	41744 KiB

cities

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define ll long long
const int MAX=1e5+10, K=1<<5;
const ll MAXV=1e18+10;/////////////
int n, k, m, spe[10];
ll dp[K][MAX];
bool odw[MAX];
vector<pair<int,ll>>g[MAX];
priority_queue<pair<ll,int>>kol;
void dijkstra(int maska){
    while(kol.size()){
        auto v=kol.top();
        kol.pop();
        v.fi*=-1;
        if(odw[v.se]) continue;
        odw[v.se]=true;
        for(auto s:g[v.se])
            if(dp[maska][s.fi]>dp[maska][v.se]+s.se)
                dp[maska][s.fi]=dp[maska][v.se]+s.se, kol.push({-dp[maska][s.fi], s.fi});
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin>>n>>k>>m;
    for(int i=1; i<=k; i++)
        cin>>spe[i-1];
    for(int i=1; i<=m; i++){
        int a, b, c;
        cin>>a>>b>>c;
        g[a].pb({b, c}), g[b].pb({a, c});
    }
    for(int i=1; i<K; i++)
        for(int j=1; j<=n; j++)
            dp[i][j]=MAXV;
    for(int i=1; i<K; i++){
        int x=i;
        vector<int>pos;
        int l=0;
        while(x){
            if(x%2) pos.pb(l);
            x/=2, l++;
        }
        if(pos.size()==1)
            dp[i][spe[pos[0]]]=0;
        for(int j=1; j<=n; j++)
            odw[j]=false;
        for(int j=1; j<=n; j++){
            for(int j1=1; j1<(1<<(int)pos.size()); j1++){
                x=j1, l=0;
                int aktMask=0;
                while(x){
                    if(x%2==1) aktMask+=(1<<(pos[l]));
                    x/=2, l++;
                }
                //cout<<i<<" "<<aktMask<<"\n";
                dp[i][j]=min(dp[i][j], dp[aktMask][j]+dp[i^aktMask][j]);
            }
            kol.push({-dp[i][j], j});
        }
        dijkstra(i);
    }
    ll mini=MAXV;
    for(int i=1; i<=n; i++)
        mini=min(mini, dp[(1<<k)-1][i]);
    cout<<mini<<"\n";
}

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