题解 | #[NOIP2001]Car的旅行路线#

题意

求从城市 A 到城市 B 的最少花费：最短路
已知一个城市 有四个机场，不妨令 A 城市中的四个机场 为 a1 , a2 , a3 , a4 ，B 城市的为 b1 , b2 , b3 , b4

又因为 各个机场彼此互通，所以本质是求:
min ( d[a1][b1], d[a1][b2], d[a1][b3], d[a1][b4], d[a2][b1], d[a2][b2], d[a2][b3], d[a2][b4], ...... , d[a4][b4] )

d[i][j]：i 点到 j 点的 “最短距离” ，即最少的花费

思路

① 建边

以每个机场为点，建立两点之间的边，边的权值为 边长（两点间距离）乘于 单位里程价格
注意：城市内的边（两点在同一个城市），和城市外的边（两点不在同一个城市） 的单位里程价格不一样

② 求最短路

因为要求得 多对 两个点之间的距离，即求多源最短路，所以使用 floyd

附图一张 from AcWing:

ps: 题目只给三个点的坐标，我们要利用矩形的性质求出第四个点的坐标

综上，Code 如下 .

Code

#include <bits/stdc++.h>

using namespace std;

const int N=410;

struct node{
    int x,y;
}p[N];  // 存每个点的坐标
double d[N][N];  // 存储两点间的距离
int a[4],b[4];  //用处 在下面标注
int x,y,x2,y2,x3,y3,x4,y4;
double t;
int s,A,B;

void find(){  // 求第四点的坐标
    int ab=(x-x2)*(x-x2)+(y-y2)*(y-y2);
    int ac=(x-x3)*(x-x3)+(y-y3)*(y-y3);
    int bc=(x2-x3)*(x2-x3)+(y2-y3)*(y2-y3);
    if (ab+ac==bc) x4=x2+x3-x, y4=y2+y3-y;
    if (ab+bc==ac) x4=x+x3-x2, y4=y+y3-y2;
    if (ac+bc==ab) x4=x+x2-x3, y4=y+y2-y3; 
}

void floyd(int n){
   for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}

int main(){
    int T;
    cin>>T;

    while(T--){
       cin>>s>>t>>A>>B;
       memset(d,0,sizeof d);
       memset(p,0,sizeof p);
       int k=1;
       for(int i=1;i<=s;i++){
          if(i>1) k+=4;
          double price;
          cin>>x>>y>>x2>>y2>>x3>>y3>>price;
          if(i==A) a[0]=k,a[1]=k+1,a[2]=k+2,a[3]=k+3; // 记录起点的四个机场的编号
          else if(i==B) b[0]=k,b[1]=k+1,b[2]=k+2,b[3]=k+3; // 记录终点的四个机场的序号

          find();
          p[k]={x,y},p[k+1]={x2,y2},p[k+2]={x3,y3},p[k+3]={x4,y4};

          d[k+1][k]=d[k][k+1]=sqrt((x-x2)*(x-x2)+(y-y2)*(y-y2))*price;
          d[k+2][k]=d[k][k+2]=sqrt((x-x3)*(x-x3)+(y-y3)*(y-y3))*price;
          d[k+2][k+1]=d[k+1][k+2]=sqrt((x3-x2)*(x3-x2)+(y3-y2)*(y3-y2))*price;
          d[k][k+3]=d[k+3][k]=sqrt((x-x4)*(x-x4)+(y-y4)*(y-y4))*price; 
          d[k+1][k+3]=d[k+3][k+1]=sqrt((x2-x4)*(x2-x4)+(y2-y4)*(y2-y4))*price ;
          d[k+2][k+3]=d[k+3][k+2]=sqrt((x3-x4)*(x3-x4)+(y3-y4)*(y3-y4))*price ;
       }

         k+=3;
         for(int i=1;i<=k;i++)
            for(int j=1;j<=k;j++)      
                 if(d[i][j]==0) {
                  int x=p[i].x,y=p[i].y;
                  int x2=p[j].x,y2=p[j].y;
                  d[j][i]=d[i][j]=sqrt((x-x2)*(x-x2)+(y-y2)*(y-y2))*t;  
              }

       floyd(k);

       double res=1e8;
       for(int i=0;i<4;i++) for(int j=0;j<4;j++)   res=min(res,d[a[i]][b[j]]); 
       printf("%.1f\n",res);
    }
    return 0;
}