求助求助求助
查看原帖
求助求助求助
664677
zzyayyz楼主2022/7/24 19:47

大佬们,能帮忙看看哪里错了吗???只有第一个点和样例过了

#include<bits/stdc++.h>
using namespace std;
int n,s,t,a,b;
float c[110];
int x[440],y[440];
float w[440][440];
float ans[110];
float zzz(int d,int g)//求距离 
{
	return sqrt(d*d+g*g);	
}
int ll(int p,int u)//建图 
{
//	int u=0;
		if(((y[4*p-3]-y[4*p-2])*(y[4*p-2]-y[4*p-1])+(x[4*p-3]-x[4*p-2])*(x[4*p-2]-x[4*p-1]))==0)
		{
		   x[4*p]=x[4*p-3]+x[4*p-1]-x[4*p-2];
		   y[4*p]=y[4*p-3]+y[4*p-1]-y[4*p-2];
		}
		if(((y[4*p-3]-y[4*p-1])*(y[4*p-2]-y[4*p-1])+(x[4*p-3]-x[4*p-1])*(x[4*p-2]-x[4*p-1]))==0)
		{
		   x[4*p]=x[4*p-3]+x[4*p-2]-x[4*p-1];
		   y[4*p]=y[4*p-3]+y[4*p-2]-y[4*p-1];
		}
		if(((y[4*p-3]-y[4*p-1])*(y[4*p-2]-y[4*p-3])+(x[4*p-3]-x[4*p-1])*(x[4*p-2]-x[4*p-3]))==0)
		{
		   x[4*p]=x[4*p-1]+x[4*p-2]-x[4*p-3];
		   y[4*p]=y[4*p-1]+y[4*p-2]-y[4*p-3];
		}
		for(int i=4*p-3;i<=4*p;i++)
		{
			for(int j=4*p-3;j<=4*p;j++)
			{
				if(i!=j)
				{w[i][j]=u*zzz(x[i]-x[j],y[i]-y[j]);
				w[j][i]=u*zzz(x[i]-x[j],y[i]-y[j]);}
				if(i==j) w[i][j]=0;
			}
		}
}
int rr(int p,int q)//判断是否一个城市 
{
	int f=0;
	if(((p-1)/4)==((q-1)/4)) f=1;
	else {f=0;}
	return f;
}
void floyed(int e)
{
	for(int i=1;i<=400;i++)
	{
		for(int j=1;j<=400;j++)
		{
			w[i][j]=0;
		}
	}
	for(int i=1;i<=101;i++)
	{
		c[i]=0; 
	} 
	cin>>s>>t>>a>>b;
	for(int i=1;i<=s;i++)
	{
		 for(int j=3;j>=1;j--)
		 {
		 	cin>>x[4*i-j]>>y[4*i-j];
		 }
		 cin>>c[i];
		 ll(i,c[i]);
	}
	for(int i=1;i<=4*s;i++)
	{
		for(int j=1;j<=4*s;j++)
		{
			if(rr(i,j)==0) {
				w[i][j]=t*zzz(x[i]-x[j],y[i]-y[j]);
			}
		}
	}
	
	for(int k=1;k<=4*s;k++)
	{
		for(int i=1;i<=4*s;i++)
		{
			if(i!=k)
		{
				for(int j=1;j<=4*s;j++)
			{
				if(i!=j&&k!=j)
			{
					if(w[i][k]+w[k][j]<w[i][j])
			{
					w[i][j]=w[i][k]+w[k][j];
			}}
		}
	}}}
	ans[e]=0x7f;
	for(int i=0;i<=3;i++)
	{
		for(int j=0;j<=3;j++)
		{
			if(ans[e]>w[4*a-i][4*b-j])
		    ans[e]=w[4*a-i][4*b-j];
		}
	}
//	cout<<ans[e]<<endl;
}
int main()
{
	//memset(w,1000000,sizeof(w));
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		floyed(i);
		//cout<<endl;
	}
	for(int i=1;i<=n;i++)
	{
		printf("%.1lf",ans[i]);
		cout<<endl;
	}
}
2022/7/24 19:47
加载中...