先只看走到樓梯的時間。用DP(Dynamic Programming)，每往上一層便去找尋到達該層所有洞的所有最短時間。出發的位置(最底層的洞)時間皆設為0，其餘的洞皆將時間設為(INT_MAX)，〖〗_=min(〖〗_, 〖〗_下層的洞+洞j到洞i的 時間) 。最後找出頂樓最小值再加上爬樓梯的時間。
Source Code(C++):
#include<iostream>
#include<string>
#include<climits>
#include<algorithm>
using namespace std;
int main(){//this problem is actually providing the distance(time) to go to the any of the ladder of current floor,while we could regard it as
string sample;//the time to climb the corresponding ladder(don't forget to add 2 minutes every floor)
int n,m;
int dist;
while(cin>>sample){
cin>>n>>m;
int ***path = new int **[n-1];//roof doesn't count,n-1
for(int count = 0;count < n-1;count++)
path[count] = new int*[m];
for(int count = 0;count < n-1;count++){
for(int index = 0;index < m;index++)
path[count][index] = new int[m];
}//using dynamic pointer array
int **DP = new int*[n];//using dynamic programming,n floor while the floor 0 are all set to 0
for(int count = 0;count < n;count++)
DP[count] = new int[m];
for(int count = 0;count < m;count++)
DP[0][count] = 0;
for(int count = 1;count < n;count++){
for(int index = 0;index < m;index++)
DP[count][index] = INT_MAX;//presume that the time to go to the holes are all infinity at the first place
}
for(int floor = 0;floor < n-1;floor++){
for(int hole = 0;hole < m;hole++){
for(int route = 0;route < m;route++)
cin>>path[floor][hole][route];
}
}
for(int floor = 1;floor < n;floor++){
for(int hole = 0;hole < m;hole++){
for(int cur = 0;cur < m;cur++){
DP[floor][hole] = min(DP[floor][hole],DP[floor-1][cur]+path[floor-1][cur][hole]); //pick the smallest time from the lower floor to get to
}//current floor by testing every (last hole+time to get to this hole)
}
}
int res = INT_MAX;
for(int hole = 0;hole < m;hole++)
res = min(res,DP[n-1][hole]);//get the smallest time of the hole of roof
cout<<sample<<endl<<res+2*(n-1)<<endl;//remember every floor consumes 2 minutes to climb on
for(int count = 0;count < n-1;count++){//release all allocated memory
for(int index = 0;index < m;index++)
delete []path[count][index];
}
for(int count = 0;count < n-1;count++)
delete []path[count];
delete []path;
for(int count = 0;count < n-1;count++)
delete []DP[count];
delete []DP;
}
return 0;
}
