UVa 1001 奶酪里的老鼠（Dijkstra或Floyd）

题意：
一个奶酪里有n个洞，老鼠在奶酪里的移动速度为10秒一个单位，但是在洞里可以瞬间移动。计算出老鼠从A点到达O点所需的最短时间。

思路：
最短路问题。

我们可以把起点和终点也看成是两个洞，半径为0。这样每个洞就代表了一个点，对于两个洞而言，圆心距离大于两半径之和，此时它们之间的距离就为圆心距离-两半径之和，否则就为0。

我们在计算出任意两个洞之间的距离之后，就可以套用最短路代码来解题了。下面的代码我是用了Floyd算法。

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 using namespace std;

 const int INF = ;

 int n;

 double d[][];

 int x[], y[], z[], r[];

 void Floyd()

 {

     for (int k = ; k <= n+;k++)

     for (int i = ; i <= n+;i++)

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

         d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

 }

 int main()

 {

     //freopen("D:\\txt.txt", "r", stdin);

     int kase = ;

     while (cin>>n && n!=-)

     {

         for (int i = ; i <= n + ;i++)

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

         if (i == j)  d[i][j] = ;

         else d[i][j] = INF;

         for (int i = ; i <= n; i++)

             cin >> x[i] >> y[i] >> z[i] >> r[i];

         for (int i = n + ; i <= n + ; i++)

         {

             cin >> x[i] >> y[i] >> z[i];

             r[i] = ;

         }

         for (int i = ; i <= n + ;i++)

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

         {

             if (i == j)  continue;

             double dis = sqrt((x[j] - x[i])*(x[j] - x[i]) + (y[j] - y[i])*(y[j] - y[i]) + (z[j] - z[i])*(z[j] - z[i]));

             dis = dis - r[j] - r[i];

             if (dis < )  dis = ;

             d[i][j] = dis;

         }

         Floyd();

         printf("Cheese %d: Travel time = %.f sec\n", ++kase,  * d[n+][n+]);

     }

 }