蒟蒻求助,#4WA
查看原帖
蒟蒻求助,#4WA
320449
forest114514楼主2023/7/19 17:33
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int N=2005;
const int M=4010000;
int n,fu[N],dis[N],head[N],ne[M],to[M],c[N],k[N],last[N],idx,tot;
LL num[M],ans=0,cnt2=0,cnt1=0;
pii d[N];bool book[N];
struct PII{
	int id;
	LL di;
	int last_id;
	bool operator <(const PII& b)const{
		return b.di<di;
	}
};
priority_queue<PII> q;
queue<int> build;
queue<pii> ans_d; 
int ManhattanDis(pii d1,pii d2){
	return abs(d1.first-d2.first)+abs(d1.second-d2.second);
}
void _add(int u,int v,LL w){
	to[++idx]=v;
	num[idx]=w;
	last[idx]=u;
	ne[idx]=head[u];
	head[u]=idx;
}
void prim(){
	memset(dis,0x3f,sizeof dis);
	dis[0]=0;
	PII o;o.di=0,o.id=0,o.last_id=-1;
	q.push(o);
	while(q.size()&&tot<=n){
		PII x=q.top();q.pop();
		if(book[x.id])continue;
		book[x.id]=1;tot++;
		ans+=x.di;
		if(x.id!=0){
			if(x.last_id){
				ans_d.push(make_pair(x.last_id,x.id));cnt1++;
			}
			else {
				build.push(x.id);cnt2++;
			}
		}
		for(int i=head[x.id];i;i=ne[i]){
			int y=to[i];
			if(dis[y]>num[i]){
				dis[y]=num[i];
				PII nw;
				nw.di=dis[y],nw.id=y,nw.last_id=last[i];
				q.push(nw);
			}
		}
	}
}
void input(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>d[i].first>>d[i].second;
	for(int i=1;i<=n;i++)cin>>c[i];
	for(int i=1;i<=n;i++)cin>>k[i];
}
void _build(){
	for(int i=1;i<=n;i++)_add(0,i,c[i]),_add(i,0,c[i]);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++) if(i!=j)
		_add(i,j,(k[i]+k[j])*ManhattanDis(d[i],d[j])),_add(j,i,(k[i]+k[j])*ManhattanDis(d[i],d[j]));
}
int main(){
	input();
	_build();
	prim();
	cout<<ans<<endl;
	cout<<cnt2<<endl;
	while(build.size()){
		cout<<build.front()<<" ";
		build.pop();
	}
	cout<<endl<<cnt1<<endl;
	while(ans_d.size()){
		cout<<ans_d.front().first<<" "<<ans_d.front().second<<endl;
		ans_d.pop(); 
	}
	return 0;
}

真不知道哪有错了,希望各位dalao能帮忙看一下吗

2023/7/19 17:33
加载中...