oj.uz

Submission #537824

# Submission time Handle Problem Language Result Execution time Memory
537824 2022-03-15T15:44:28 Z __Variatto Cities (BOI16_cities) C++17
100 / 100
 2138 ms 41744 KB 
#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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 2 ms 2812 KB Output is correct
5 Correct 2 ms 2804 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1173 ms 41596 KB Output is correct
2 Correct 1109 ms 40792 KB Output is correct
3 Correct 851 ms 34496 KB Output is correct
4 Correct 85 ms 12100 KB Output is correct
5 Correct 980 ms 41680 KB Output is correct
6 Correct 87 ms 12096 KB Output is correct
7 Correct 9 ms 3284 KB Output is correct
8 Correct 7 ms 3260 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3156 KB Output is correct
2 Correct 8 ms 3284 KB Output is correct
3 Correct 7 ms 3200 KB Output is correct
4 Correct 6 ms 3028 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1504 ms 41584 KB Output is correct
2 Correct 1434 ms 40736 KB Output is correct
3 Correct 1032 ms 34448 KB Output is correct
4 Correct 821 ms 27724 KB Output is correct
5 Correct 224 ms 15300 KB Output is correct
6 Correct 77 ms 14204 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2138 ms 41568 KB Output is correct
2 Correct 2107 ms 41744 KB Output is correct
3 Correct 2056 ms 40828 KB Output is correct
4 Correct 1447 ms 34624 KB Output is correct
5 Correct 1119 ms 27820 KB Output is correct
6 Correct 276 ms 15516 KB Output is correct
7 Correct 81 ms 14592 KB Output is correct