[UVA][dp] 10350 - Liftless EME
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
Sample0013 21 23 45 67 8
Sample Output
Sample001
10
Mustaq Ahmed
題目描述：
「每層樓都挖洞放個梯子可以到下一層，那麼從底
才發現原來是因為每層洞的位置不一樣，
移動到另外一個洞的正下方所
題目解法：
DAG 使用 DP，或者使用最短路。
#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;
}