UVa 1001 - Say Cheese

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

在一個三維空間中的乳酪,知道乳酪常會有氣泡般的空洞,假設在空洞中任意位置之間移動不消耗時間,為了抵達目的地,可以啃食乳酪到另外一個空洞,啃食時間與距離 1 : 1 關係,請問最少時間為何。

Sample Input

1
2
3
4
5
6
7
8
9
1
20 20 20 1
0 0 0
0 0 10
1
5 0 0 4
0 0 0
10 0 0
-1

Sample Output

1
2
Cheese 1: Travel time = 100 sec
Cheese 2: Travel time = 20 sec

Solution

建圖解決。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
int main() {
int n, x[128], y[128], z[128], r[128];
int cases = 0;
while (scanf("%d", &n) == 1 && n >= 0) {
for (int i = 0; i < n + 2; i++) {
if (i < n)
scanf("%d %d %d %d", &x[i], &y[i], &z[i], &r[i]);
else
scanf("%d %d %d", &x[i], &y[i], &z[i]), r[i] = 0;
}
n += 2;
double f[128][128];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) f[i][i] = 0;
else {
double dist = sqrt(pow(x[i]-x[j], 2) + pow(y[i]-y[j], 2) + pow(z[i] - z[j], 2));
if (dist <= r[i] + r[j])
f[i][j] = 0;
else
f[i][j] = dist - (r[i] + r[j]);
}
}
}
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
printf("Cheese %d: Travel time = %.0lf sec\n", ++cases, f[n-1][n-2] * 10);
}
return 0;
}