fork(42) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define f first
  5. #define s second
  6. pair<int,int> a[10000];
  7. int d[20000];
  8. int k[20000];
  9. int32_t main(){
  10.   int n;
  11.   cin>>n;
  12.   for(int x,y,i=0;i<n;i++){
  13.      cin>>x>>y;
  14.      a[i].f=x;
  15.      a[i].s=y;
  16.   }
  17.   for(int i=0;i<n;i++){
  18.     int x;cin>>x;
  19.     d[i]=x;
  20.   }
  21.   for(int i=0;i<n;i++){
  22.     int y; cin>>y;
  23.     k[i]=y;
  24.   }
  25.   priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > pq;
  26.   int c[10000]={0};
  27.   for(int i=0;i<n;i++) c[i]=i;
  28.   for(int i=0;i<n;i++){
  29.     pq.push({d[i],i});
  30.   }
  31.   int ct[20000];
  32.   while(!pq.empty()){
  33.      pair<int,int> p=pq.top();
  34.      for(int i=0;i<n;i++){
  35.        if(i==p.s || i==c[p.s]) continue;
  36.        int dist=abs(a[i].f-a[p.s].f)+abs(a[i].s-a[p.s].s);
  37.        if(d[i]>((k[p.s]+k[i])*dist) ){
  38.          d[i]=((k[p.s]+k[i])*dist);
  39.          pq.push({d[i],i});
  40.          c[i]=c[p.s];
  41.          ct[i]=p.s;
  42.        }
  43.      }
  44.      pq.pop();
  45.   }
  46.   int ans=0;
  47.   for(int i=0;i<n;i++){
  48.     ans+=d[i];
  49.   }
  50.   cout<<ans<<"\n";
  51.   int ps=0,con=0;
  52.   vector<int> v;
  53.   vector<pair<int,int> > edge;
  54.   for(int i=0;i<n;i++){
  55.     if(c[i]==i){
  56.       ps++;
  57.       v.push_back(i+1);
  58.     }
  59.     else {
  60.       con++;
  61.       edge.push_back({i,ct[i]});
  62.     }
  63.   }
  64.   cout<<ps<<"\n";
  65.   for(int i=0;i<v.size();i++){
  66.     cout<<v[i]<<" ";
  67.   }
  68.   cout<<"\n";
  69.   cout<<con<<"\n";
  70.   for(int i=0;i<edge.size();i++){
  71.     cout<<edge[i].f+1<<" "<<edge[i].s+1<<"\n";
  72.   }
  73. }
Success #stdin #stdout 0s 4380KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
0

0
https://ideone.com/tRcPzZ
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!