http://codeforces.com/contest/1245/problem/D
#include <bits/stdc++.h> //#include <cmath> //#include <iostream> //#include <unordered_map> #define lowbit(x) ((x)&(-x)) #define mem(x,y) memset(x,y,sizeof(x)) #define pb push_back #define INF 0x3f3f3f3f #define ll long long #define FAST_IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); using namespace std; const int mod=1e9+7; const int N=2e3+9; int n; struct C { int x,y; }p[N]; ll c[N],k[N]; struct E { int from,to; ll w; }edge[N*N+N]; int tot; void addedge(int u,int v,ll w) { edge[tot].from=u; edge[tot].to=v; edge[tot].w=w; tot++; } bool cmp(E a, E b) { return a.w<b.w; } int fa[N]; int Find(int x) { return fa[x]==x?x:fa[x]=Find(fa[x]); } ll dis(C a,C b) { return (ll)abs(a.x-b.x)+(ll)abs(a.y-b.y); } vector<pair<int,int> > ans; vector<int> ans2; ll kru() { ll sum=0; sort(edge,edge+tot,cmp); for(int i=0;i<tot;i++) { int u=edge[i].from; int v=edge[i].to; int ju=Find(u); int jv=Find(v); ll w=edge[i].w; //cout<<ju<<jv<<endl; if(ju!=jv) { if(u!=0&&v!=0) ans.pb({u,v}); if(u==0||v==0) { if(u==0) ans2.pb(v); else ans2.pb(u); } fa[jv]=ju; sum+=w; } } return sum; } int main() { FAST_IO; cin>>n; for(int i=1;i<=n;i++) { cin>>p[i].x>>p[i].y; } for(int i=0;i<=n;i++) fa[i]=i; for(int i=1;i<=n;i++) cin>>c[i]; for(int i=1;i<=n;i++) cin>>k[i]; for(int i=1;i<=n;i++) { addedge(0,i,c[i]); } for(int i=1;i<=n;i++) { for(int j=i+1;j<=n;j++) { addedge(i,j,dis(p[i],p[j])*(k[i]+k[j])); addedge(j,i,dis(p[i],p[j])*(k[i]+k[j])); } } ll sum=kru(); cout<<sum<<endl; cout<<ans2.size()<<endl; for(int i=0;i<ans2.size();i++) cout<<ans2[i]<<" "; cout<<endl; cout<<ans.size()<<endl; for(int i=0;i<ans.size();i++) cout<<ans[i].first<<" "<<ans[i].second<<endl; return 0; }
