24h購物| | PChome| 登入
2013-07-31 18:33:13| 人氣2,113| 回應0 | 上一篇 | 下一篇

[UVA][dp] 10350 - Liftless EME

推薦 0 收藏 0 轉貼0 訂閱站台

Problem F

Liftless EME

Input: standard input

Output: standard output

Time Limit: 2 seconds

Memory Limit: 32 MB

The EME building has grown taller and taller from the year 2002 to 2020. But the number of lifts has remained constant. As a result, it has become a great problem for the students to reach their classes in time. Especially the contestants of ACM Preparation Contest are suffering very much. Their contest starts at exactly 2:00pm on every Tuesday and at that time, the lifts and the stairs are packed with lab-going students.

So the contestants decided to make some shortcut path to the ACM Lab. They secretly made some holes through the roofs of their classrooms and placed a ladder in each hole, so that they can move from one room of a floor to a room in the next floor without pushing the crowd.

This made a new problem for them: they have so many holes and some of the shortcut paths take much more time to traverse.

You are to find out the path from the ground floor (0-th floor) to the (n-1)-th floor that can be reached in shortest possible time. The contestants never climb down a ladder (except when the contest is over).

Input

Input consists of several test cases.

Each case consists of the case name (consisting of up to 12 alphanumeric characters) in a line followed by a line with two integers n (the number of roofs in the EME building, except the topmost roof) and m (number of holes through each roof). The next m(n-1) lines each contains m integers. The j-th integer in the(km+i)-th line (where 0 £ k < n-1 < 120, 1 £ i, j £ m £ 15) is the time (in minutes) needed to walk from the i-th hole through the roof of k-th floor (i.e. the i-th hole through the floor of (k+1)-th floor) to the ladder at the j-th hole through the roof of (k+1)-th floor. It takes 2 minutes to climb each ladder, but you shouldn't consider the time needed by the ladders at the ground floor.

Input in terminated by end of file.

Output

For each data set, print 2 lines: The first line is the case name and the second line is the minimum time needed to reach the (n-1)-th floor.

Sample Input

Sample001
3 2
1 2
3 4
5 6
7 8

Sample Output

Sample001
10

Mustaq Ahmed


題目描述：
「每層樓都挖洞放個梯子可以到下一層，那麼從底部爬到頂樓最少時間為多少？」
才發現原來是因為每層洞的位置不一樣，因此輸入在說明從這個洞爬上去之後，
移動到另外一個洞的正下方所花費的時間。


題目解法：
DAG 使用 DP，或者使用最短路。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int d[150][20][20];
int dp[150][20];
int main() {
    int i, j, k;
    int n, m;
    char s[105];
    while(scanf("%s", s) == 1) {
        scanf("%d %d", &n, &m);
        for(i = 0; i < n-1; i++) {//i-floor
            for(j = 0; j < m; j++) {//i-floor j-hole
                for(k = 0; k < m; k++) {//i-floor j-hole to i+1-floor k-hole
                    scanf("%d", &d[i][j][k]);
                }
            }
        }
        memset(dp[0], 0, sizeof(dp[0]));
        for(i = 0; i < n-1; i++) {
            memset(dp[i+1], 63, sizeof(dp[i+1]));
            for(j = 0; j < m; j++) {
                for(k = 0; k < m; k++) {
                    dp[i+1][k] = min(dp[i+1][k], dp[i][j]+d[i][j][k]);
                }
            }
        }
        int ret = 0xfffffff;
        for(i = 0; i < m; i++)
            ret = min(ret, dp[n-1][i]);
        puts(s);
        printf("%d\n", ret + 2*n-2);
    }
    return 0;
}

我要檢舉
#10350#Liftless EME#dp
台長： Morris

您可能對以下文章有興趣

人氣(2,113) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 教育學習(進修、留學、學術研究、教育概況) | 個人分類: UVA |
此分類下一篇:[UVA][dp] 986 - How Many
此分類上一篇:[UVA][DP] 10259 - Hippity Hopscotch

我要回應
否 是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼：
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文