开始做这题的时候总是将它和最小生成树算法混淆，最短路径初始的时候是存的从其点到其他各点的距离，没有的设为无穷，每次都是找出最短的路径值（同时标记该顶点，说明已经找到了最短的路径，不需要再修改），并且不断修改起点到其他各点的距离，如此循环，知知道所有顶点都访问；
//思路：本质是找从 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
雪黛依梦 阅读(388)
评论(0) 编辑 收藏 引用 所属分类:
最小生成树