紫书习题 11-2 UVa 1001 （Floyd）

这道题只是在边上做一些文章。

这道题起点终点可以看成半径为0的洞，我是直接加入了洞的数组。

边就是两点间的距离减去半径，如果结果小于0的话，距离就为0，距离不能为负

然后我看到n只有100，范围很小，虽然这道题只是单源最短路，

但是Floyd代码比较短，而又不会超时，所以我就写了Floyd。

#include<cstdio>

#include<algorithm>

#include<vector>

#include<cmath>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

const int MAXN = 112;

struct node

{

	int x, y, z, r;

	node(int x = 0, int y = 0, int z = 0, int r = 0) : x(x), y(y), z(z), r(r) {};

}hole[MAXN];

double d[MAXN][MAXN];

double dist(int i, int j)

{

	double t = sqrt(pow(hole[i].x-hole[j].x, 2) + pow(hole[i].y-hole[j].y, 2) + pow(hole[i].z-hole[j].z, 2));

	return max(t - hole[i].r - hole[j].r, 0.0);

}

int main()

{

	int kase = 0, x, y, z, n;

	while(~scanf("%d", &n) && n != -1)

	{

		n += 2;

		REP(i, 0, n)

		{

			scanf("%d%d%d", &hole[i].x, &hole[i].y, &hole[i].z);

			if(i < n - 2) scanf("%d", &hole[i].r);

			else hole[i].r = 0;

		}

		REP(i, 0, n)

			REP(j, 0, n)

				d[i][j] = dist(i, j);	

		REP(k, 0, n)

			REP(i, 0, n)

				REP(j, 0, n)

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

		printf("Cheese %d: Travel time = %d sec\n", ++kase, (int)(d[n-1][n-2] * 10 + 0.5));

	}

	return 0;

}

巴特西

紫书习题 11-2 UVa 1001 （Floyd）

最新文章

热门文章

巴特西

紫书 习题 11-2 UVa 1001 （Floyd）

最新文章

热门文章

紫书习题 11-2 UVa 1001 （Floyd）