fork(42) download
  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
stdin
Standard input is empty
stdout
0
0

0