最短路之 CODE[VS] 1041 Car的旅行路线 2001年NOIP全国联赛提高组-白红宇

最短路之 CODE[VS] 1041 Car的旅行路线 2001年NOIP全国联赛提高组

阅读量：4598 次

发布时间：2019-06-09

本文共 3560 字，大约阅读时间需要 11 分钟。

/*Floyd算法：最短路 关键：	（1）求出矩形第四个点坐标（判断垂直交点，向量加）		已知矩形的A、B、C点的坐标，求D点坐标：			若 |AB|^2 + |AC|^2 = |BC|^2，则：A点即为垂直交点			向量(A->B) + 向量(A->C) = 向量(A->D)			=> D.x = A.x + 向量(A->D).x			  D.y = A.y + 向量(A->D).y	（2）建图 */

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             
               10 #include 
              
                11 #include 
               
                 12 #include 
                 13 #include 
                 
                   14 #include 
                  
                    15 #include 
                   
                     16 #include 
                    
                      17 #include 
                     
                       18 using namespace std; 19 typedef pair
                      
                        P; 20 const int INF = 0x3f3f3f3f; 21 const int modPrime = 3046721; 22 const double eps = 1e-9; 23 const int MaxN = 105; 24 25 int n, s, A, B; 26 double t; 27 double T[MaxN]; 28 29 double dp[MaxN][MaxN]; 30 31 struct Point 32 { 33 int x, y; 34 }; 35 36 vector
                       
                         cityPoint[MaxN]; 37 38 39 int disSquare(const Point p1, const Point p2) 40 { 41 return (p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y); 42 } 43 44 int verticalPoint(const Point pt[]) 45 { 46 int dis01, dis02, dis12; 47 dis01 = disSquare(pt[0], pt[1]); 48 dis02 = disSquare(pt[0], pt[2]); 49 dis12 = disSquare(pt[1], pt[2]); 50 51 if (dis01 + dis02 == dis12) return 0; 52 if (dis01 + dis12 == dis02) return 1; 53 if (dis02 + dis12 == dis01) return 2; 54 55 return -1; 56 } 57 58 void iniCity(int city) 59 { 60 Point pt[4]; 61 scanf("%d %d %d %d %d %d %lf", &pt[0].x, &pt[0].y, &pt[1].x, &pt[1].y, &pt[2].x, &pt[2].y, &T[city]); 62 63 int vtcPt = verticalPoint(pt); 64 65 pt[3].x = pt[vtcPt].x + ((pt[(vtcPt + 1) % 3].x - pt[vtcPt].x) + (pt[(vtcPt + 2) % 3].x - pt[vtcPt].x)); 66 pt[3].y = pt[vtcPt].y + ((pt[(vtcPt + 1) % 3].y - pt[vtcPt].y) + (pt[(vtcPt + 2) % 3].y - pt[vtcPt].y)); 67 68 for (int i = 0; i < 4; ++i) 69 { 70 cityPoint[city].push_back(pt[i]); 71 } 72 73 for (int i = 0; i < 4; ++i) 74 { 75 for (int j = i; j < 4; ++j) 76 { 77 if (i != j) 78 { 79 dp[i + (city << 2)][j + (city << 2)] = T[city] * sqrt(1.0*disSquare(pt[i], pt[j])); 80 dp[j + (city << 2)][i + (city << 2)] = dp[i + (city << 2)][j + (city << 2)]; 81 } 82 else 83 { 84 dp[i + (city << 2)][j + (city << 2)] = 0.0; 85 } 86 } 87 } 88 } 89 90 void iniMap() 91 { 92 for (int i = 0; i < s; ++i) 93 { 94 for (int j = i + 1; j < s; ++j) 95 { 96 for (int m = 0; m < 4; ++m) 97 { 98 for (int n = 0; n < 4; ++n) 99 {100 dp[m + (i << 2)][n + (j << 2)] = t*sqrt(1.0*disSquare(cityPoint[i][m], cityPoint[j][n]));101 dp[n + (j << 2)][m + (i << 2)] = dp[m + (i << 2)][n + (j << 2)];102 }103 }104 }105 }106 }107 108 void Solve()109 {110 int pointSum = (s << 2);111 for (int k = 0; k < pointSum; ++k)112 {113 for (int i = 0; i < pointSum; ++i)114 {115 for (int j = 0; j < pointSum; ++j)116 {117 dp[i][j] = min(dp[i][j], dp[i][k] + dp[j][k]);118 }119 }120 }121 }122 123 void getAns()124 {125 double ans = INF * 1.0;126 for (int i = 0; i < 4; ++i)127 {128 for (int j = 0; j < 4; ++j)129 {130 ans = min(ans, dp[i + ((A - 1) << 2)][j + ((B - 1) << 2)]);131 }132 }133 printf("%.1lf\n", ans);134 }135 136 137 int main()138 {139 #ifdef HOME140 freopen("in", "r", stdin);141 //freopen("out", "w", stdout);142 #endif143 144 scanf("%d", &n);145 while (n--)146 {147 scanf("%d %lf %d %d", &s, &t, &A, &B);148 for (int i = 0; i < s; ++i)149 {150 iniCity(i);151 }152 iniMap();153 Solve();154 getAns();155 for (int i = 0; i < s; ++i)156 {157 cityPoint[i].clear();158 }159 }160 161 #ifdef HOME162 cerr << "Time elapsed: " << clock() / CLOCKS_PER_SEC << " ms" << endl;163 _CrtDumpMemoryLeaks();164 #endif165 return 0;166 }