蒟蒻求助,第四个点
查看原帖
蒟蒻求助,第四个点
362167
b1468821672楼主2023/7/16 10:08
#include<iostream>
#include<queue>
#include<cmath>
using namespace std;
const int N=2e3+10;
const long long INF=1e18;
int n,cnt,ans,num,num2;
int head[N*N];
int x[N],y[N],city[N],rc[N][2];
long long c[N],k[N],dis[N];
bool vis[N],vised[N][N];
struct edge
{
	int to,nxt;
	long long w;
}e[N*N];
struct node
{
	int id;
	long long ans;
	bool operator <(const node &x)const
	{
		return x.ans<ans;
	}
};
priority_queue<node> q;
void addedge(int u,int v,long long w)
{
	e[++cnt].to=v;
	e[cnt].w=w;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}
void dijkstra(int s)
{
	dis[s]=0;
	q.push((node){s,0});
	while(!q.empty())
	{
		int u=q.top().id;
		q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(int i=head[u];i;i=e[i].nxt)
		{
			int v=e[i].to;
			if(dis[v]>dis[u]+e[i].w)
			{
				dis[v]=dis[u]+e[i].w;
				if(!vis[v])
				{
					q.push((node){v,dis[v]});
				 } 
			}
		}
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>x[i]>>y[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(n+1,i,c[i]);
		dis[i]=INF;
		for(int j=1;j<i;j++)
		{
			long long z=abs(x[i]-x[j])+abs(y[i]-y[j]);
			z*=(k[i]+k[j]);
			addedge(i,j,z);
			addedge(j,i,z);
	    }
	}
	dijkstra(n+1);
	for(int i=1;i<=n;i++)
	if(dis[i]==c[i])city[++num]=i,ans+=c[i];
	for(int i=1;i<=n;i++)
	for(int j=i+1;j<=n;j++)
	if(abs(dis[i]-dis[j])==(abs(x[i]-x[j])+abs(y[i]-y[j]))*(k[i]+k[j]))
	{
		ans+=abs(dis[i]-dis[j]);
		rc[++num2][1]=i;
		rc[num2][2]=j;
		break;
	}
	cout<<ans<<endl;
	cout<<num<<endl;
	for(int i=1;i<=num;i++)
	cout<<city[i]<<' ';
	cout<<endl<<num2<<endl;
	for(int i=1;i<=num2;i++)
	cout<<rc[i][1]<<" "<<rc[i][2]<<endl;
	return 0;
}
2023/7/16 10:08
加载中...