P1027 car的旅行路线

car的旅行路线

洛谷链接

这个题关键就是

如何把每个点表示出来，其实求出四个点的坐标后，只需要把这些点连接起来，用一遍folyed求出最短路径就好了。

代码：

 #include<cmath>

 #include<cstdio>

 int x[],y[];//x表示横坐标，y表示纵坐标

 int ti[];//在第i个城市中铁路单位里程价格

 int n,s,tt,a,b;//tt表示航线单位里程价格

 double d[][];//i到j的长度（花费）

 void doit(int t1,int t2){//计算t1到t2的花费

     d[t1][t2]=sqrt((x[t1]-x[t2])*(x[t1]-x[t2])

                 +(y[t1]-y[t2])*(y[t1]-y[t2]));//求t1到t2的长度

     if (((t1-)/)==((t2-)/)){//判断t1，t2是否在同一个城市内

         d[t1][t2]=d[t1][t2]*ti[(t1-)/+];//计算花费

     }else

         d[t1][t2]=d[t1][t2]*tt;

     d[t2][t1]=d[t1][t2];//对称

     return;//结束

 }

 int find(int t1,int t2,int t3){//找直角三角形斜边

     //如果一边长度大于任意两边返回此边对着的点

     if((d[t1][t2]>d[t2][t3])&&(d[t1][t2]>d[t3][t1])) return t3;

     //t1t2对应的点为t3

     if((d[t2][t3]>d[t1][t2])&&(d[t2][t3]>d[t3][t1])) return t1;

     //t2t3对应的点为t1

     if((d[t3][t1]>d[t2][t3])&&(d[t3][t1]>d[t1][t2])) return t2;

     //t1t3对应的点为t2

 }

 void doit2(int t1,int t2,int t3){

     doit(t1,t2);//t1到t2的花费（比在同一城市）

     doit(t2,t3);//t2到t3的花费（必在同一城市）

     doit(t3,t1);//t3到t1的花费（必在同一城市）

     int haha=find(t1,t2,t3);//找此直角三角形的斜边

     //而在平行四边形中

     //一条边的两个顶点的横（或纵）坐标的差值

     //等于其对边两个顶点的横（或纵）坐标的差值

     if(haha==t1){//看斜边对着的点为哪个，并求出第4个点的坐标

         x[t3+]=x[t3]+x[t2]-x[t1];

         y[t3+]=y[t3]+y[t2]-y[t1];

     }

     else if(haha==t2){

         x[t3+]=x[t3]+x[t1]-x[t2];

         y[t3+]=y[t3]+y[t1]-y[t2];

     }

     else if(haha==t3){

         x[t3+]=x[t1]+x[t2]-x[t3];

         y[t3+]=y[t1]+y[t2]-y[t3];

     }

 }

 int main(){

     scanf("%d",&n);

     for(;n>=;n--){//循环运行n次

         scanf("%d %d %d %d",&s,&tt,&a,&b);

         //S城市数，t飞机单价，A，B序号

         int i,j,k;

         for(i=;i<=;i++)//初始化

             for(j=;j<=;j++)

                 d[i][j]=;

         for(i=;i<=s;i++){

             scanf("%d%d%d%d%d%d%d",

             &x[*i-],&y[*i-],&x[*i-],

             &y[*i-],&x[*i-],&y[*i-],

             &ti[i]);

             doit2(*i-,*i-,*i-);

         }

         for(i=;i<=*s;i++)

             for(j=;j<=*s;j++)

             doit(i,j);//计算i到j的花费

         for(k=;k<=*s;k++)

             for(i=;i<=*s;i++)

                 for(j=;j<=*s;j++)

                     if(d[k][j]+d[i][k]<d[i][j])

                         d[i][j]=d[k][j]+d[i][k];//Floyed

         double ans=200000000.0;

         for(i=*a-;i<=*a;i++)

             for(j=*b-;j<=*b;j++)

                 if(d[i][j]<ans)

                     ans=d[i][j];//更新最小值

         printf("%.1lf\n",ans);//输出，并保留一位小数

     }

     return ;

 }