首页 > itarticle > uva 1011 – crossing the desert

uva 1011 – crossing the desert

admin 11月 11, 2020 0

contents

Problem

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

Sample Input

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 儲存)。最後一趟，則不考慮回程，額外可以增加攜帶食物量。

#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 foodn", 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
*/