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