#4 WA
查看原帖
#4 WA
1044914
yejuncenyyds楼主2023/9/5 12:17
#include<bits/stdc++.h>
using namespace std;
long long n,g[2005][2005],k[2005],c[2005]={0x7ffff},c1[2005],total=0,dad[2005],cityal=0,city[2005],city2al=0,city2[2005];
bool leaf[2005];
struct zb{
	int x,y;
}a[2005];
void find_dad(int k){
	for(int i=1;i<=n;i++) if(leaf[i]&&g[k][i]!=0&&g[k][i]==c[k]&&c1[k]!=c[k]){
		dad[k]=i;
		return;
	}
	dad[k]=k;
}
void prim(){
	for(int i=1;i<=n;i++){
		int k=0;
		for(int j=1;j<=n;j++) if(!leaf[j]&&c[j]<c[k]) k=j;
		leaf[k]=1;
		total++;
		find_dad(k);
		for(int j=1;j<=n;j++) if(!leaf[j]&&g[k][j]!=0) c[j]=min(g[k][j],c[j]);
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
	for(int i=1;i<=n;i++){
	cin>>c[i];
	c1[i]=c[i];
	}
	for(int i=1;i<=n;i++)cin>>k[i];
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){
		if(i!=j){
			g[i][j]=(k[i]+k[j])*(abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y));
		}
	}
	while(total<=n) prim();
	int sum=0;
	for(int i=1;i<=n;i++){
	sum+=c[i];	
	if(dad[i]==i)city[++cityal]=i;
	if(dad[i]!=i){
	  city2[i]=dad[i];
	  city2al++;	
	}
	}
	cout<<sum<<endl;
	cout<<cityal<<endl;
	for(int i=1;i<=cityal;i++) cout<<city[i]<<" ";	
	cout<<endl<<city2al<<endl;
	if(city2al!=0) for(int i=1;i<=n;i++) if(city2[i]){
	cout<<i<<" "<<city2[i]<<endl;
	city2[city2[i]]=0;
	} 
}
2023/9/5 12:17
加载中...