oj.uz

Submission #926559

# Submission time Handle Problem Language Result Execution time Memory
926559 2024-02-13T09:39:13 Z irmuun Cities (BOI16_cities) C++17
100 / 100
 2892 ms 51904 KB 
#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()

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n,k,m;
    cin>>n>>k>>m;
    ll dp[32][n];
    int p[k];
    vector<pair<int,ll>>adj[n];
    for(int i=0;i<k;i++){
        cin>>p[i];
        p[i]--;
    }
    for(int i=0;i<m;i++){
        int a,b;
        ll c;
        cin>>a>>b>>c;
        a--,b--;
        adj[a].pb({b,c});
        adj[b].pb({a,c});
    }
    for(int i=0;i<(1<<k);i++){
        for(int j=0;j<n;j++){
            dp[i][j]=1e18;
        }
    }
    for(int i=0;i<k;i++){
        dp[1<<i][p[i]]=0;
    }
    for(int c=0;c<(1<<k);c++){
        for(int a=0;a<c;a++){
            if((a|c)!=c) continue;
            int b=a^c;
            if(b>a) continue;
            for(int i=0;i<n;i++){
                dp[c][i]=min(dp[c][i],dp[a][i]+dp[b][i]);
            }
        }
        set<pair<ll,int>>st;
        vector<bool>used(n,0);
        for(int i=0;i<n;i++){
            if(dp[c][i]<1e18){
                st.insert({dp[c][i],i});
            }
        }
        while(!st.empty()){
            auto [d,i]=*st.begin();
            st.erase(st.begin());
            if(used[i]==true) continue;
            used[i]=true;
            for(auto [j,C]:adj[i]){
                ll cost=C+d;
                if(cost<dp[c][j]){
                    dp[c][j]=cost;
                    st.insert({dp[c][j],j});
                }
            }
        }
    }
    ll ans=1e18;
    for(int i=0;i<n;i++){
        ans=min(ans,dp[(1<<k)-1][i]);
    }
    cout<<ans;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 638 ms 51060 KB Output is correct
2 Correct 607 ms 51904 KB Output is correct
3 Correct 263 ms 41344 KB Output is correct
4 Correct 47 ms 12872 KB Output is correct
5 Correct 310 ms 50796 KB Output is correct
6 Correct 44 ms 12884 KB Output is correct
7 Correct 3 ms 860 KB Output is correct
8 Correct 2 ms 860 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 856 KB Output is correct
2 Correct 5 ms 860 KB Output is correct
3 Correct 3 ms 604 KB Output is correct
4 Correct 3 ms 604 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1343 ms 51392 KB Output is correct
2 Correct 1417 ms 51856 KB Output is correct
3 Correct 667 ms 41428 KB Output is correct
4 Correct 711 ms 33612 KB Output is correct
5 Correct 168 ms 17336 KB Output is correct
6 Correct 53 ms 14928 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2892 ms 51660 KB Output is correct
2 Correct 2863 ms 51636 KB Output is correct
3 Correct 2744 ms 51524 KB Output is correct
4 Correct 1418 ms 41464 KB Output is correct
5 Correct 1431 ms 33964 KB Output is correct
6 Correct 279 ms 17332 KB Output is correct
7 Correct 61 ms 15172 KB Output is correct