oj.uz

Submission #937177

# Submission time Handle Problem Language Result Execution time Memory
937177 2024-03-03T15:08:41 Z 1075508020060209tc Cities (BOI16_cities) C++14
100 / 100
 1413 ms 37708 KB 
#include<bits/stdc++.h>
//#include<bits/extc++.h>
using namespace std;
//using namespace __gnu_pbds;
#define int long long
int n;int K;int m;
int imp[8];
vector<pair<int,int>>e[100005];
 
void dijkstera(vector<int>ost,vector<int>&dis){
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
for(int i:ost){
    pq.push({dis[i],i});
}
bitset<100005>vis;
while(pq.size()){
    int nw=pq.top().second;
    pq.pop();
    if(vis[nw]){continue;}
    vis[nw]=1;
    for(auto pr:e[nw]){
        int v=pr.first;
        int w=pr.second;
        if(vis[v]){continue;}
        if(dis[v]>dis[nw]+w){
            dis[v]=dis[nw]+w;
            pq.push({dis[v],v});
        }
    }
}
}
 
vector<int>disa[6];
vector<int>disab[6][6];
void init(){
cin>>n>>K>>m;
for(int i=1;i<=K;i++){
    cin>>imp[i];
    disa[i].resize(n+10,0);
}
 
 
 
for(int i=1;i<=m;i++){
    int a;int b;int c;
    cin>>a>>b>>c;
    e[a].push_back({b,c});
    e[b].push_back({a,c});
}
}
 
int prm[6];
int slv5(){
int ret=1e18;
for(int i=1;i<=n;i++){
    int clc=1e18;
    clc=min(clc,disab[1][2][i]+min({disa[3][i]+disab[4][5][i],disa[4][i]+disab[3][5][i],disa[5][i]+disab[3][4][i]}));
    clc=min(clc,disab[1][3][i]+min({disa[2][i]+disab[4][5][i],disa[4][i]+disab[2][5][i],disa[5][i]+disab[2][4][i]}));
    clc=min(clc,disab[1][4][i]+min({disa[2][i]+disab[3][5][i],disa[3][i]+disab[2][5][i],disa[5][i]+disab[2][3][i]}));
    clc=min(clc,disab[1][5][i]+min({disa[2][i]+disab[3][4][i],disa[3][i]+disab[2][4][i],disa[4][i]+disab[2][3][i]}));
 
    clc=min(clc,disab[2][3][i]+disa[1][i]+disab[4][5][i]);
    clc=min(clc,disab[2][4][i]+disa[1][i]+disab[3][5][i]);
    clc=min(clc,disab[2][5][i]+disa[1][i]+disab[3][4][i]);
 
    ret=min(ret,clc);
}
return ret;
}
 
 
signed main(){
init();
for(int i=1;i<=K;i++){
    for(int j=1;j<=n;j++){
        disa[i][j]=1e16;
    }
    disa[i][imp[i]]=0;
    vector<int>vc={imp[i]};
    dijkstera(vc,disa[i]);
}
if(K==2){
    cout<<disa[1][imp[2]];return 0;
}
for(int i=1;i<=K;i++){
    for(int j=i+1;j<=K;j++){
        //if(i==j){continue;}
        disab[i][j].resize(n+10);
        vector<int>vc;
        for(int v=1;v<=n;v++){
            disab[i][j][v]=disa[i][v]+disa[j][v];
            vc.push_back(v);
        }
        dijkstera(vc,disab[i][j]);
    }
}
 
int ans=1e18;
if(K==4&&n<=1000){
    vector<vector<int>>dis2(n+2,vector<int>(n+2,1e16));
    for(int a=1;a<=n;a++){
        dis2[a][a]=0;
        dijkstera({a},dis2[a]);
    }
 
    for(int a=1;a<=n;a++){
            ans=min(ans,disa[1][a]+disa[2][a]+disa[3][a]+disa[4][a]);
        for(int b=1;b<=n;b++){
            ans=min(ans,dis2[a][b]+min(dis2[a][imp[1]],dis2[b][imp[1]])+min(dis2[a][imp[2]],dis2[b][imp[2]])+min(dis2[a][imp[3]],dis2[b][imp[3]])+min(dis2[a][imp[4]],dis2[b][imp[4]])  );
        }
    }
    cout<<ans;return 0;
}
/*
if(K==5&&n<=1000){
    vector<vector<int>>dis2(n+2,vector<int>(n+2,1e16));
    for(int a=1;a<=n;a++){
        dis2[a][a]=0;
        dijkstera({a},dis2[a]);
    }
 
    for(int a=1;a<=n;a++){
            ans=min(ans,disa[1][a]+disa[2][a]+disa[3][a]+disa[4][a]+disa[5][a]);
        for(int b=1;b<=n;b++){
            ans=min(ans,dis2[a][b]+min(dis2[a][imp[1]],dis2[b][imp[1]])+min(dis2[a][imp[2]],dis2[b][imp[2]])+min(dis2[a][imp[3]],dis2[b][imp[3]])+min(dis2[a][imp[4]],dis2[b][imp[4]])+min(dis2[a][imp[5]],dis2[b][imp[5]]));
        }
    }
    for(int a=1;a<=n;a++){
        for(int b=1;b<=n;b++){
            for(int c=1;c<=n;c++){
                int abc=min({dis2[a][b]+dis2[a][c],dis2[a][b]+dis2[b][c],dis2[a][c]+dis2[c][b]});
                int clc=0;
                for(int i=1;i<=5;i++){
                    clc+=min({dis2[a][imp[i]],dis2[b][imp[i]],dis2[c][imp[i]]});
                }
                ans=min(ans,clc+abc);
            }
        }
    }
    cout<<ans;return 0;
}*/
 
if(K==3){
    ans=disab[1][2][imp[3]];
    cout<<ans<<endl;
    return 0;
}
vector<int>fdis(n+10,0);
if(K==4){
    for(int i=1;i<=n;i++){
        ans=min({ans,disab[1][2][i]+disab[3][4][i],disab[1][3][i]+disab[2][4][i],disab[1][4][i]+disab[2][3][i]});
    }
    cout<<ans<<endl;
    return 0;
}
ans=slv5();
cout<<ans;
 
 
}

Subtask #1
22.0 / 22.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 475 ms 26220 KB Output is correct
2 Correct 401 ms 26460 KB Output is correct
3 Correct 188 ms 17796 KB Output is correct
4 Correct 127 ms 11856 KB Output is correct
5 Correct 226 ms 16580 KB Output is correct
6 Correct 134 ms 11856 KB Output is correct
7 Correct 3 ms 2904 KB Output is correct
8 Correct 2 ms 2908 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 10892 KB Output is correct
2 Correct 149 ms 11000 KB Output is correct
3 Correct 43 ms 10840 KB Output is correct
4 Correct 55 ms 4952 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 658 ms 30288 KB Output is correct
2 Correct 578 ms 30148 KB Output is correct
3 Correct 341 ms 21152 KB Output is correct
4 Correct 387 ms 21836 KB Output is correct
5 Correct 183 ms 13336 KB Output is correct
6 Correct 1413 ms 17660 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 857 ms 34488 KB Output is correct
2 Correct 870 ms 37708 KB Output is correct
3 Correct 807 ms 36496 KB Output is correct
4 Correct 484 ms 27192 KB Output is correct
5 Correct 535 ms 27432 KB Output is correct
6 Correct 211 ms 17600 KB Output is correct
7 Correct 149 ms 17300 KB Output is correct