開始做這題的時候總是將它和最小生成樹算法混淆，最短路徑初始的時候是存的從其點到其他各點的距離，沒有的設為無窮，每次都是找出最短的路徑值（同時標記該頂點，說明已經找到了最短的路徑，不需要再修改），并且不斷修改起點到其他各點的距離，如此循環，知知道所有頂點都訪問；
//思路：本質是找從 A 到 B 的最短路徑，如果最短路徑存在則一定會用滿足題意的按最少次數的按鈕
//如果最短路徑不存在肯定找不到，輸出 -1
//這里將可以到達的點設為 1, 是因為如果可以到達就按了一下按鈕，如果不可到達則仍然是MAX
//此題中如果有某一個點找不到到達它的最短路徑，說明電梯到達這一層之后不可能再達到其他任何了，所以return返回主函數檢查；這是和模板不同的地方
#include <iostream>
#include <string>
using namespace std;
#define MAXN 99999999
int button[201]; //存儲每一層按下按鈕之后可升降的層數
int map[201][201];
int dist[201];
int visit[201];
int n, a, b;
void dijkstra ()
{
for (int i = 1; i <= n; i ++)
{
dist[i] = map[a][i]; //初值是起點到每個點的距離！
}
dist[a] = 0;
int k, min;
for ( int i = 1; i <= n; i ++ )
{
min = MAXN;
for (int j = 1; j <= n; j ++)
{
if ( !visit[j] && dist[j] < min ) //找最短的距離
{
min = dist[j];
k = j;
}
}
if ( min == MAXN ) //沒有最短路了 // 順序
return ;
visit[k] = 1;
for (int j = 1; j <= n; j ++)
{
if ( !visit[j] && map[k][j] + dist[k] < dist[j] )
{
dist[j] = map[k][j] + dist[k];
}
}
}
}
int main ()
{
while ( scanf ("%d", &n) != EOF && n )
{
scanf ( "%d %d", &a, &b );
memset ( button, 0, sizeof (button) );
memset ( dist, 0, sizeof (dist) );
memset ( visit, 0, sizeof (visit) );
for ( int i = 1; i <= n; i ++ )
{
for ( int j = 1; j <= n; j ++ )
{
map[i][j] = MAXN;
}
}
for ( int i = 1; i <= n; i ++ )
{
scanf ("%d", &button[i]);
if ( i + button[i] <= n )
{
map[i][i + button[i]] = 1;
}
if ( i - button[i] >= 1 ) //最大的錯誤不是else if啊！！！！
{
map[i][i - button[i]] = 1;
}
}
dijkstra ();
if ( dist[b] < MAXN ) //有路徑到達
printf ("%d\n", dist[b]);
else
printf ("%d\n", -1);
}
//system ("pause");
return 0;
}
posted on 2010-08-26 20:38
雪黛依夢 閱讀(401)
評論(0) 編輯 收藏 引用 所屬分類:
最小生成樹