#include <stdio.h> int main() { int n, i, j, k, E; while (scanf("%d %d", &n, &E) == 2) { getchar(); int t[100]; for (i = 0; i < n; i++) { scanf("%d", &t[i]); getchar(); } int max[5] = {}, d[5][100], visit[5][100] = {}, ok[5][100] = {}; for (i = 0; i < 5; i++) for (j = 0; j < 100; j++) d[i][j] = 1e9; for (i = 0; i < n; i++) { char temp[200]; gets(temp); int sum = 0; for (j = 0; ; j++) if ('0' <= temp[j] && temp[j] <= '9') { sum = sum * 10 + temp[j] - '0'; } else { ok[i][sum] = 1; max[i] = sum > max[i] ? sum : max[i]; if (!sum) d[i][0] = 0; sum = 0; if (!temp[j]) break; } } int ans = -1; while (1) { int type = -1, h, min = 1e9; for (i = 0; i < n; i++) for (j = 0; j <= max[i]; j++) if (ok[i][j] && !visit[i][j] && d[i][j] < min) { min = d[i][j]; type = i; h = j; } if (type == -1) break; if (h == E) { ans = min; break; } visit[type][h] = 1; for (i = 0; i < n; i++) for (j = 0; j <= max[i]; j++) if (ok[i][j] && !visit[i][j]) { int w = d[type][h] + t[i] * ((j - h) < 0 ? (h - j) : (j - h)); if (i == type) { if (w < d[i][j]) d[i][j] = w; } else if (j == h) { if (w + 60 < d[i][j]) d[i][j] = w + 60; } } } if (ans != -1) printf("%d\n", ans); else puts("IMPOSSIBLE"); } return 0; }
Hello, I am a CS student from Taiwan.
I am learing English and Programming.
I'll save source code of some problems or small programs without comments in this blog.
I would recommend you not to read solution from others before you solved the problem.
(這邊專門存放沒有任何註解的小程式/OJ題目程式碼)
2012年11月21日
UVa 10801 - Lift Hopping
訂閱:
張貼留言 (Atom)
沒有留言:
張貼留言