[NOIP2001]Car的旅行路线

第一行为一个正整数n( 0 ≤ n ≤ 10 )，表示有n组测试数据。
每组的第一行有4个正整数S,t,A,B。
S( 0 < S ≤ 100 )表示城市的个数，t表示飞机单位里程的价格，A，B分别为城市A，B的序号，( 1 ≤ A，B ≤ S )。
接下来有S行，其中第i行均有7个正整数 xi₁,yi₁,xi₂,yi₂,xi₃,yi₃,T_i这当中的(xi₁,yi₁)，(xi₂,yi₂)，(xi₃,yi₃)分别是第i个城市中任意3个机场的坐标，T_i为第i个城市高速铁路单位里程的价格。

C++(clang++ 11.0.1) 解法, 执行用时: 3ms, 内存消耗: 532K, 提交时间: 2022-10-03 21:26:06

#include<bits/stdc++.h>
using namespace std;
const int N=410;
double d[N][N];
int n,fee,S,E,t;
struct Node{int x,y,fee;}a[N*4];
struct City{int x[4],y[4],price;}city[110];
double getDist(int x,int y,int x1,int y1){
	double xx=x-x1,yy=y-y1;
	return sqrt(xx*xx+yy*yy);
}
void getCity4(City &a){
	double d[3];
	for(int i=0,k=0;i<3;i++)for(int j=i+1;j<3;j++)d[k++]=getDist(a.x[i],a.y[i],a.x[j],a.y[j]);
	double maxx=max({d[0],d[1],d[2]});
	for(int i=0;i<3;i++)
		if(maxx==d[i]){
			int k=2-i,x=0,y=0;
			for(int j=0;j<3;j++)if(j!=k)x+=a.x[j],y+=a.y[j];
			a.x[3]=x-a.x[k],a.y[3]=y-a.y[k];
			break;
		}
}
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d%d%d%d",&n,&fee,&S,&E);
		S--,E--;
		for(int i=1;i<=n;i++){
			for(int j=0;j<3;j++)scanf("%d%d",&city[i].x[j],&city[i].y[j]);
			scanf("%d",&city[i].price);
			getCity4(city[i]);
			for(int j=0;j<4;j++)a[(i-1)*4+j+1]={city[i].x[j],city[i].y[j],city[i].price};
		}
		for(int i=1;i<=4*n;i++)
			for(int j=i+1;j<=4*n;j++)
				if((i-1)/4==(j-1)/4)d[i][j]=d[j][i]=a[i].fee*getDist(a[i].x,a[i].y,a[j].x,a[j].y);
				else d[i][j]=d[j][i]=fee*getDist(a[i].x,a[i].y,a[j].x,a[j].y);
		for(int k=1;k<=4*n;k++)for(int i=1;i<=4*n;i++)for(int j=1;j<=4*n;j++)d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
		double res=1e18;
		for(int i=1;i<=4;i++)for(int j=1;j<=4;j++)res=min(res,d[S*4+i][E*4+j]);
		printf("%.1lf\n",res);
	}
}

详情