MiYu原創(chuàng), 轉(zhuǎn)帖請注明 : 轉(zhuǎn)載自 ______________白白の屋
題目地址:
http://acm.hdu.edu.cn/showproblem.php?pid=1548
題目描述:
A strange lift
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2641 Accepted Submission(s): 944
Problem Description
There is a strange lift.The lift can stop can at every floor as you want, and there is a number Ki(0 <= Ki <= N) on every floor.The lift have just two buttons: up and down.When you at floor i,if you press the button "UP" , you will go up Ki floor,i.e,you will go to the i+Ki th floor,as the same, if you press the button "DOWN" , you will go down Ki floor,i.e,you will go to the i-Ki th floor. Of course, the lift can't go up high than N,and can't go down lower than 1. For example, there is a buliding with 5 floors, and k1 = 3, k2 = 3,k3 = 1,k4 = 2, k5 = 5.Begining from the 1 st floor,you can press the button "UP", and you'll go up to the 4 th floor,and if you press the button "DOWN", the lift can't do it, because it can't go down to the -2 th floor,as you know ,the -2 th floor isn't exist.
Here comes the problem: when you is on floor A,and you want to go to floor B,how many times at least he havt to press the button "UP" or "DOWN"?
Input
The input consists of several test cases.,Each test case contains two lines.
The first line contains three integers N ,A,B( 1 <= N,A,B <= 200) which describe above,The second line consist N integers k1,k2,
.kn.
A single 0 indicate the end of the input.
Output
For each case of the input output a interger, the least times you have to press the button when you on floor A,and you want to go to floor B.If you can't reach floor B,printf "-1".
Sample Input
5 1 5
3 3 1 2 5
0
Sample Output
3
題目分析:
這題又是一個標(biāo)準(zhǔn)的 Dijkstra 算法的題目 ( 最短路 ). 要說難度嗎? 對我而言吧, 就是 圖的生成.
剛開始做的時候自己想復(fù)雜了, 以為從不同的樓層開始, 就有不同的走法, 所以開始的時候?qū)懷h(huán)沒寫對,
就寫成了遞歸. 結(jié)果很杯具的 STACK_OVERFLOW........ 在 AMB 神牛的指點發(fā)現(xiàn), 原來是自己想復(fù)雜了,
只需要計算出每一個樓層的 上樓 和 下樓就可以了, 當(dāng)然, 要注意是否越界. 圖生成后, 當(dāng)然就是 DIJKSTRA了.
閑來無事, 又復(fù)制一遍 :
Dijkstra算法的基本思路是：
假設(shè)每個點都有一對標(biāo)號 (dj, pj)，其中dj是從起源點s到點j的最短路徑的長度 (從頂點到其本身的最短路徑是零路(沒有弧的路)，其長度等于零)；
pj則是從s到j(luò)的最短路徑中j點的前一點。求解從起源點s到點j的最短路徑算法的基本過程如下：
1) 初始化。起源點設(shè)置為：① ds=0, ps為空;② 所有其他點: di=∞, pi=?;③ 標(biāo)記起源點s，記k=s,其他所有點設(shè)為未標(biāo)記的。
2) 檢驗從所有已標(biāo)記的點k到其直接連接的未標(biāo)記的點j的距離，并設(shè)置：
dj=min［dj, dk+lkj］
式中，lkj是從點k到j(luò)的直接連接距離。
3) 選取下一個點。從所有未標(biāo)記的結(jié)點中，選取dj 中最小的一個i：
di=min［dj, 所有未標(biāo)記的點j］
點i就被選為最短路徑中的一點，并設(shè)為已標(biāo)記的。
4) 找到點i的前一點。從已標(biāo)記的點中找到直接連接到點i的點j*，作為前一點,設(shè)置：i=j*
5) 標(biāo)記點i。如果所有點已標(biāo)記，則算法完全推出，否則，記k=i，轉(zhuǎn)到2) 再繼續(xù)。
代碼如下:
#include <iostream>
using namespace std;
const int MAX = 200;
const int INF = 0x7FFFFFF;
int N,A,B;
int g[MAX+1][MAX+1];
int hash[MAX+1];
int path[MAX+1];
int K[MAX+1];
int Dijkstra ( int beg , int end )
{
path[beg] = 0;
hash[beg] = false;
while ( beg != end )
{
int m = INF, temp;
for ( int i = 1; i <= N; ++ i )
{
if ( g[beg][i] != INF )
path[i] = min ( path[i], path[beg] + g[beg][i] );
if ( m > path[i] && hash[i] )
{
m = path[i];
temp = i;
}
}
beg = temp;
if ( m == INF )
break;
hash[beg] = false;
}
if ( path[end] == INF )
return -1;
return path[end];
}
int main ()
{
while ( scanf ( "%d%d%d", &N, &A, &B ) , N )
{
for ( int i = 0; i <= MAX; ++ i )
{
hash[i] = true;
path[i] = INF;
for ( int j = 0; j <= MAX; ++ j )
{
g[i][j] = INF;
}
}
for ( int i = 1; i <= N; ++ i )
{
scanf ( "%d",&K[i] );
}
for ( int i = 1; i <= N; ++ i )
{
if ( i + K[i] <= N )
g[ i ][ i + K[i] ] = 1;
if ( i - K[i] >= 1 )
g[ i ][ i - K[i] ] = 1;
}
cout << Dijkstra ( A, B ) << endl;
}
return 0;
}
SO 代碼:
#include <iostream>
using namespace std;
const int MAX = 200;
const int INF = 0x7FFFFFF;
bool UP = true;
bool DOWN = false;
int N,A,B;
int g[MAX+1][MAX+1];
int hash[MAX+1];
int path[MAX+1];
int K[MAX+1];
int Dijkstra ( int beg , int end )
{
path[beg] = 0;
hash[beg] = false;
while ( beg != end )
{
int m = INF, temp;
for ( int i = 1; i <= N; ++ i )
{
if ( g[beg][i] != INF )
path[i] = min ( path[i], path[beg] + g[beg][i] );
if ( m > path[i] && hash[i] )
{
m = path[i];
temp = i;
}
}
beg = temp;
if ( m == INF )
break;
hash[beg] = false;
}
if ( path[end] == INF )
return -1;
return path[end];
}
bool setGraph ( int n, bool flag )
{
if ( flag )
{
if ( n + K[n] <= N )
{
g[ n ][ n + K[n] ] = 1;
setGraph ( n + K[n], UP );
setGraph ( n + K[n], DOWN );
}
}
else
{
if ( n - K[n] >= 1 )
{
g[ n ][ n - K[n] ] = 1;
setGraph ( n - K[n], UP );
setGraph ( n - K[n], DOWN );
}
}
return true;
}
int main ()
{
while ( scanf ( "%d%d%d", &N, &A, &B ) , N )
{
for ( int i = 0; i <= MAX; ++ i )
{
hash[i] = true;
path[i] = INF;
for ( int j = 0; j <= MAX; ++ j )
{
g[i][j] = INF;
}
}
for ( int i = 1; i <= N; ++ i )
{
scanf ( "%d",&K[i] );
}
for ( int i = 1; i <= N; ++ i )
{
setGraph ( i, UP );
setGraph ( i, DOWN );
}
cout << Dijkstra ( A, B ) << endl;
}
return 0;
}