oj.uz

Submission #697946

# Submission time Handle Problem Language Result Execution time Memory
697946 2023-02-11T14:42:55 Z FEDIKUS Cities (BOI16_cities) C++17
100 / 100
 2119 ms 51492 KB 
#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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 5076 KB Output is correct
5 Correct 3 ms 5204 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 658 ms 28144 KB Output is correct
2 Correct 680 ms 27820 KB Output is correct
3 Correct 412 ms 20120 KB Output is correct
4 Correct 162 ms 14128 KB Output is correct
5 Correct 461 ms 24988 KB Output is correct
6 Correct 159 ms 14060 KB Output is correct
7 Correct 6 ms 5204 KB Output is correct
8 Correct 7 ms 5224 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5400 KB Output is correct
2 Correct 8 ms 5404 KB Output is correct
3 Correct 7 ms 5332 KB Output is correct
4 Correct 7 ms 5332 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1119 ms 34476 KB Output is correct
2 Correct 1139 ms 38368 KB Output is correct
3 Correct 716 ms 28548 KB Output is correct
4 Correct 689 ms 29776 KB Output is correct
5 Correct 292 ms 20712 KB Output is correct
6 Correct 185 ms 20000 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2119 ms 47196 KB Output is correct
2 Correct 2109 ms 51492 KB Output is correct
3 Correct 2049 ms 50900 KB Output is correct
4 Correct 1359 ms 41204 KB Output is correct
5 Correct 1132 ms 36384 KB Output is correct
6 Correct 355 ms 22208 KB Output is correct
7 Correct 228 ms 20048 KB Output is correct