oj.uz

Submission #926560

# Submission time Handle Problem Language Result Execution time Memory
926560 2024-02-13T09:40:39 Z irmuun Cities (BOI16_cities) C++17
100 / 100
 4129 ms 44236 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;
        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());
            for(auto [j,C]:adj[i]){
                ll cost=C+d;
                if(cost<dp[c][j]){
                    if(dp[c][j]<1e18){
                        st.erase({dp[c][j],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 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 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 784 ms 44208 KB Output is correct
2 Correct 699 ms 43320 KB Output is correct
3 Correct 283 ms 39072 KB Output is correct
4 Correct 48 ms 9300 KB Output is correct
5 Correct 357 ms 44236 KB Output is correct
6 Correct 43 ms 9308 KB Output is correct
7 Correct 3 ms 860 KB Output is correct
8 Correct 2 ms 724 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 860 KB Output is correct
2 Correct 6 ms 892 KB Output is correct
3 Correct 4 ms 600 KB Output is correct
4 Correct 4 ms 604 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1653 ms 44088 KB Output is correct
2 Correct 1547 ms 43432 KB Output is correct
3 Correct 741 ms 39508 KB Output is correct
4 Correct 944 ms 26916 KB Output is correct
5 Correct 191 ms 11928 KB Output is correct
6 Correct 58 ms 11604 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4129 ms 44220 KB Output is correct
2 Correct 3892 ms 44072 KB Output is correct
3 Correct 3525 ms 43152 KB Output is correct
4 Correct 1944 ms 39284 KB Output is correct
5 Correct 1896 ms 26920 KB Output is correct
6 Correct 316 ms 12272 KB Output is correct
7 Correct 66 ms 11856 KB Output is correct