解題區/解題區 - UVa

UVa 1011 - Crossing the Desert

contents

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

Problem

在一個沙漠中，有 N 個綠洲，每一個綠洲只有水源可以獲取使用，食物可以從起點城鎮帶過來存放，但是綠洲本身不帶有食物獲取，每走一步將會損耗單位水和食物，身上負重最多 W，你可以攜帶一部分食物放置在綠洲，然後走回起點再帶食物過來存放，要推進到終點，至少要從城鎮中購買多少食物。

Sample Input

1
2
3
4
5
6
7
8
9
4 100
10 -20
-10 5
30 15
15 35
2 100
0 0
100 100
0 0

Sample Output

1
2
3
Trial 1: 136 units of food
Trial 2: Impossible

Solution

很簡單想的，我們只能從終點逆推回來，我們考慮綠洲 u 到終點 end 的最少食物花費 cost_u，現在考慮從 v 點到 u 再到 end，如果 cost_u 加上 e(v, u) 的花費不超過負重，則可以得知直接從 v 攜帶 cost_u 的食物量。

如果 cost_u 太大，則表示必須來來往往於 u, v 之間，而每一趟 v->u->v，攜帶路徑花費 1 倍水、 2 倍食物 (在 u 那邊打水即可)，剩下的空間為一次運送的食物量 (放置在 u 儲存)。最後一趟，則不考慮回程，額外可以增加攜帶食物量。

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <math.h>
using namespace std;
#define eps 1e-8
int main() {
    int n, m;
    int cases = 0;
    while (scanf("%d %d", &n, &m) == 2 && n+m) {
        double x[50], y[50];
        double g[50][50];
        double dp[50];
        int used[50] = {};
        for (int i = 0; i < n; i++) {
            scanf("%lf %lf", &x[i], &y[i]);
            dp[i] = 1e+6;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                double d = hypot(x[i] - x[j], y[i] - y[j]);
                g[i][j] = d;
            }
        }
        dp[n-1] = 0;
        for (int i = 0; i < n; i++) {
            int u = -1;
            for (int j = 0; j < n; j++) {
                if (used[j] == 0 && (u == -1 || dp[u] > dp[j]))
                    u = j;
            }
            used[u] = 1;
            for (int j = 0; j < n; j++) {
                if (used[j])	continue;
                double w = g[u][j];
                if (m >= dp[u] + 2 * w)
                    dp[j] = min(dp[j], dp[u] + w);
                else if (m >= 3 * w) {
                    int times = ceil((dp[u] - (m - 2 * w))/ (m - 3 * w));
                    dp[j] = min(dp[j], dp[u] + times * (2 * w) + w);
                }
            }
        }
        printf("Trial %d: ", ++cases);
        if (dp[0] != 1e+6)
            printf("%.0lf units of food\n", ceil(dp[0]));
        else
            puts("Impossible");
        puts("");
    }
    return 0;
}
/*
4 100
10 -20
-10 5
30 15
15 35
2 100
0 0
100 100
0 0
*/