解題區/解題區 - UVa

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;
}