首页 > 代码库 > UVa 1001 奶酪里的老鼠(Dijkstra或Floyd)

UVa 1001 奶酪里的老鼠(Dijkstra或Floyd)

https://vjudge.net/problem/UVA-1001

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

 

思路:
最短路问题。

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

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

 1 #include<iostream>  2 #include<algorithm> 3 #include<cstring> 4 #include<cmath> 5 using namespace std; 6  7 const int INF = 1000000; 8  9 int n;10 double d[105][105];11 int x[105], y[105], z[105], r[105];12 13 void Floyd()14 {15     for (int k = 1; k <= n+2;k++)16     for (int i = 1; i <= n+2;i++)17     for (int j = 1; j <= n+2; j++)18         d[i][j] = min(d[i][j], d[i][k] + d[k][j]);19 }20 21 int main()22 {23     //freopen("D:\\txt.txt", "r", stdin);24     int kase = 0;25     while (cin>>n && n!=-1)26     {27         for (int i = 1; i <= n + 2;i++)28         for (int j = 1; j <= n + 2;j++)29         if (i == j)  d[i][j] = 0;30         else d[i][j] = INF;31 32         for (int i = 1; i <= n; i++)33             cin >> x[i] >> y[i] >> z[i] >> r[i];34         for (int i = n + 1; i <= n + 2; i++)35         {36             cin >> x[i] >> y[i] >> z[i];37             r[i] = 0;38         }39 40         for (int i = 1; i <= n + 2;i++)41         for (int j = 1; j <= n + 2; j++)42         {43             if (i == j)  continue;44             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]));45             dis = dis - r[j] - r[i];46             if (dis < 0)  dis = 0;47             d[i][j] = dis;48         }49         Floyd();50         printf("Cheese %d: Travel time = %.f sec\n", ++kase, 10 * d[n+1][n+2]);51     }52 }

 

UVa 1001 奶酪里的老鼠(Dijkstra或Floyd)