题意 求某城到某城的最小花费

一个城中有四个机场，一个城中的机场相互可达，用公路到达，但是不同城的公路的单位路程的

费不同，两个不同城的机场（我不知道相同城可不可以）可以通过机场到达，且飞机单位路程价格

一定，问从 a 城到b城的最小花费，可从a的任一机场出发，从 b 的任一机场结束 。

题解 这道题思路还算容易，就是求最短路，只是建图比较麻烦，

总体思路

1、建图

（1） 相同城 的四个机场两两连线 求距离，

【1】但是他只给出了三个点，也就是说这第四个点要我们自己求

首先他给出三个点，这三个点一定构成一个直角三角形，因为四个点构成的是矩形

【2】然后我们就可以求三角形的最长边，最长边即斜边，斜边对应的顶点即为直角顶点

【3】 然后知道直角顶点，就可以用平移法则算出第四个点的坐标了

（2） 然后任意两个机场两两连线，模拟飞机到达，我不知道相同城是否可以用飞机到达，反正

我是当他可以的。

（3）这样建图建好了，然后跑一遍floyd 最短路就行了

注意这题边多点少，边是满的，所以建议用floyd 多源最短路，不建议用 SPFA

 

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 using namespace std ;10 11 const int inf = 700000000 ;12 struct node{13 double x,y ;14 };15 node e[101] ;16 int n,a,b,t,tt,cnt,tz ;17 double mi ;18 double f[101][101],dist[101][101] ;19 20 inline double sqr(double x)21 {22 return x*x;23 }24 25 inline void ce(int t1,int t2) // 计算两点间的直线距离 26 {27 double d = sqrt ( sqr(e[t1].x-e[t2].x) + sqr(e[t1].y-e[t2].y) ) ;28 dist[t1][t2] = d ;29 dist[t2][t1] = d ;30 }31 32 inline int calc(int t1,int t2,int t3) // 返回 斜边对应的直角顶点 33 {34 if(dist[t1][t2]>dist[t1][t3]&&dist[t1][t2]>dist[t2][t3]) return t3 ;35 if(dist[t1][t3]>dist[t1][t2]&&dist[t1][t3]>dist[t2][t3]) return t2 ;36 if(dist[t2][t3]>dist[t1][t3]&&dist[t2][t3]>dist[t1][t2]) return t1 ; 37 } 38 39 inline void add(int t1,int t2,int t3,int w ) // 计算四点中第四个点的坐标 40 {41 ce(t1,t2) ;42 ce(t2,t3) ;43 ce(t3,t1) ;44 int xie = calc(t1,t2,t3) ;45 if (xie==t2) swap(t1,t2) ; 46 if (xie==t3) swap(t1,t3) ; 47 e[ w ].x = e[t2].x+e[t3].x-e[t1].x ;48 e[ w ].y = e[t2].y+e[t3].y-e[t1].y ; 49 }50 51 inline void pree() 52 {53 cnt = 0 ;54 for(int i=1;i<=100;i++) e[i].x = 0,e[i].y = 0 ;55 56 }57 58 int main() 59 {60 scanf("%d",&tz) ;61 for(int v=1;v<=tz;v++) 62 {63 pree() ; 64 scanf("%d%d%d%d",&n,&t,&a,&b ) ;65 for(int i=1;i<=100;i++)66 for(int j=1;j<=100;j++) dist[ i ][ j ] = inf ;67 for(int i=1;i<=n;i++) 68 {69 for(int j=1;j<=3;j++) 70 ++cnt,scanf("%lf%lf",&e[cnt].x,&e[cnt].y) ; 71 ++cnt ;72 add(cnt-3,cnt-2,cnt-1,cnt) ;73 scanf("%d",&tt) ;74 for(int j=cnt-3;j<=cnt-1;j++)75 for(int k =j+1;k<=cnt;k++)76 ce(j,k),dist[j][k]=dist[j][k]*tt,dist[k][j]=dist[k][j]*tt ; 77 }78 for(int i=1;i<=cnt;i++)79 for(int j=1;j<=cnt;j++) f[ i ][ j ] = dist[ i ][ j ] ;80 for(int i=1;i<=cnt;i++)81 for(int j=1;j<=cnt;j++)82 {83 ce(i,j) ;84 if(dist[i][j]*t
             
              f[i][j]) mi = f[i][j] ;94 printf("%.1lf\n",mi) ;95 96 }97 return 0 ;98 }