首先，让我骂一句那没事找事的Car 还取一个那么奇怪的名字 看到这个题，恕我直言，我们明显可以看出这是一道图的最短路问题。由于这个题的数据范围很小（s只有100），所以在这里我们选取时间复杂度为O(n3)的Floyd主要是好写。
相信大家都想得到这些，其实这道题最大的难点在预处理所以我刚才说了一大堆废话，针对他给出的每个城市，我们应该如何处理呢?
首先是读入
int a,b; scanf("%d%d%d%d",&n,&tf,&a,&b); for(int i=1;i<=4*n;i++) for(int j=1;j<=4*n;j++) e[i][j]=inf; for(int i=1;i<=n;i++) { for(int j=1;j<=6;j++) scanf("%d",wz[i]+j); for(int j=1;j<=5;j+=2) { wz[i][7]+=wz[i][j]; wz[i][8]+=wz[i][j+1]; } scanf("%d",wz[i]+9);这里用了一个wz[][]数组，wz[i][j]（j=1，3，5，7）表示第i座城市的四个点的横坐标，wz[i][j]（j=2，4，6，8）表示第i座城市的四个点的纵坐标，而j=9则是路费。其中wz[i][7]与wz[i][8]是要去计算的。 而怎么算呢？我们可以得到一个公式xd=xa+xb-xc。 （y类似）（我们可以知道，已知的三点肯定是一个直角三角形，而（xa，ya）是TA的直角顶点，（xd，yd）便是TA所对的点。公式证明留给读者去思考。提示：利用两对角线交点是中点，然后使用中点坐标公式。）但我们还需要知道谁是直角顶点，这里很明显可以利用勾股定理求解。（当然还可以使用斜率乘积等于-1，但作者血与泪的教训还是建议你不要尝试。也可能是我太菜了）
计算代码
double tp[3]; int tp2=inf,tp3; tp[0]=dist1(wz[i][4],wz[i][6],wz[i][3],wz[i][5]); tp[1]=dist1(wz[i][2],wz[i][6],wz[i][1],wz[i][5]); tp[2]=dist1(wz[i][2],wz[i][4],wz[i][1],wz[i][3]); if(tp[0]+tp[1]==tp[2]){//我在之前把wz[i][7]处理成wz[i][1,3,5]的和， //这里直接减两倍横纵坐标 wz[i][7]-=2*wz[i][5];wz[i][8]-=2*wz[i][6]; } else if(tp[1]+tp[2]==tp[0]){ wz[i][7]-=2*wz[i][1];wz[i][8]-=2*wz[i][2]; } else if(tp[0]+tp[2]==tp[1]){ wz[i][7]-=2*wz[i][3];wz[i][8]-=2*wz[i][4]; } }这是dis1函数
double dist(int a,int b,int c,int d){ return sqrt((a-b)*(a-b)*1.0+1.0*(c-d)*(c-d)); }然后枚举构造某城市之间飞机场的边。（这里我把城市里的每个顶点当一个点）
for(int i=1;i<=n;i++) { for(int j=1;j<=4;j++) for(int k=j;k<=4;k++) { int u=(i-1)*4+j,v=(i-1)*4+k;//记得减一 double dis=dist(wz[i][j*2-1],wz[i][k*2-1],wz[i][j*2],wz[i][k*2]); e[u][v]=e[v][u]=dis*wz[i][9]; } }dist函数（与dist1的唯一区别就是开了根号）
double dist(int a,int b,int c,int d){ return sqrt((a-b)*(a-b)*1.0+1.0*(c-d)*(c-d)); }接下来便是城市间最短距离的代码
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i!=j){//关键！！！作者调了一小时(┬＿┬) for(int k=1;k<=4;k++) for(int l=1;l<=4;l++) { int u=(i-1)*4+k,v=(j-1)*4+l; double dis=dist(wz[i][k*2-1],wz[j][l*2-1],wz[i][k*2],wz[j][l*2]); e[u][v]=dis*tf; } }然后便是我们期待已久的Floyd
for(int k=1;k<=n*4;k++) for(int i=1;i<=n*k;i++) for(int j=1;j<=n*4;j++) if(e[i][j]>e[i][k]+e[k][j]) e[i][j]=e[i][k]+e[k][j];最后枚举起点终点，找到最短路
ouble ans=inf; for(int i=(a-1)*4+1;i<=a*4;i++) for(int j=(b-1)*4+1;j<=b*4;j++) ans=min(ans,e[i][j]); printf("%.1lf",ans);是不是很简单？ 害我调了半天，万恶的Car 最后给出完整代码
#include<bits/stdc++.h> using namespace std; const int maxn=100005,maxm=500005,inf=0x3f3f3f3f; double e[1005][1005]; int wz[1005][11]; int n,tf; double dist(int a,int b,int c,int d){ return sqrt((a-b)*(a-b)*1.0+1.0*(c-d)*(c-d)); } double dist1(int a,int b,int c,int d){ return (a-b)*(a-b)*1.0+1.0*(c-d)*(c-d); } int main() { int t; cin>>t; while(t--) { int a,b; scanf("%d%d%d%d",&n,&tf,&a,&b); for(int i=1;i<=4*n;i++) for(int j=1;j<=4*n;j++) e[i][j]=inf; for(int i=1;i<=n;i++) { for(int j=1;j<=6;j++) scanf("%d",wz[i]+j); for(int j=1;j<=5;j+=2) { wz[i][7]+=wz[i][j]; wz[i][8]+=wz[i][j+1]; } scanf("%d",wz[i]+9); double tp[3]; int tp2=inf,tp3; tp[0]=dist1(wz[i][4],wz[i][6],wz[i][3],wz[i][5]); tp[1]=dist1(wz[i][2],wz[i][6],wz[i][1],wz[i][5]); tp[2]=dist1(wz[i][2],wz[i][4],wz[i][1],wz[i][3]); if(tp[0]+tp[1]==tp[2]){ wz[i][7]-=2*wz[i][5];wz[i][8]-=2*wz[i][6]; } else if(tp[1]+tp[2]==tp[0]){ wz[i][7]-=2*wz[i][1];wz[i][8]-=2*wz[i][2]; } else if(tp[0]+tp[2]==tp[1]){ wz[i][7]-=2*wz[i][3];wz[i][8]-=2*wz[i][4]; } } for(int i=1;i<=n;i++) { for(int j=1;j<=4;j++) for(int k=j;k<=4;k++) { int u=(i-1)*4+j,v=(i-1)*4+k; double dis=dist(wz[i][j*2-1],wz[i][k*2-1],wz[i][j*2],wz[i][k*2]); e[u][v]=e[v][u]=dis*wz[i][9]; } } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i!=j){ for(int k=1;k<=4;k++) for(int l=1;l<=4;l++) { int u=(i-1)*4+k,v=(j-1)*4+l; double dis=dist(wz[i][k*2-1],wz[j][l*2-1],wz[i][k*2],wz[j][l*2]); e[u][v]=dis*tf; } } for(int k=1;k<=n*4;k++) for(int i=1;i<=n*k;i++) for(int j=1;j<=n*4;j++) if(e[i][j]>e[i][k]+e[k][j]) e[i][j]=e[i][k]+e[k][j]; double ans=inf; for(int i=(a-1)*4+1;i<=a*4;i++) for(int j=(b-1)*4+1;j<=b*4;j++) ans=min(ans,e[i][j]); printf("%.1lf",ans); } return 0; }