| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 937120 | 1075508020060209tc | Cities (BOI16_cities) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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});
}
}
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){
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){
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]])+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({dis[a][b]+dis[a][c],dis[a][b]+dis[b][c],dis[a][c]+dis[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;
}
ans=disab[1][2][imp[3]];
cout<<ans<<endl;
}