A strange lift

简介:

点击打开链接

题意:有n层楼层,如今在每一层有两个button,分别为up和down,按动button时,能够向上或向下跳动num[ i ]层;问是否能以最少的次数从A到B层,不能输出-1;

解析:构图,将从i层到按动button后跳转的楼层。看作连通状态,赋值为1,这样就转换成单源最短路问题;

#include<iostream>
#include<cstring>
#include<cstdio>

using namespace std;

const int maxn = 500;
const int Max = 0x3f3f3f3f;
int num[ maxn ], mapp[ maxn ][ maxn ], dis[ maxn ], vis[ maxn ];
int n, start, end;
	
void Dijkstra( int start ){
	memset( vis, 0, sizeof( vis ) );
	vis[ start ] = 1;
	for( int i = 1; i <= n; ++i ){
		dis[ i ] = mapp[ start ][ i ];
	}
/*	for( int i = 0; i <= n; ++i ){
		cout << dis[ i ] << endl;
	}*/
	dis[ start ] = 0;
	for( int i = 1; i <= n; ++i ){
		int temp = Max, k;
		for( int j = 1; j <= n; ++j ){
			if( !vis[ j ] && temp > dis[ j ] ){
				temp = dis[ k = j ];
			}
		}
		if( temp == Max )
			break;
		vis[ k ] = 1;
		for( int j = 1; j <= n; ++j ){
			if( !vis[ j ] && dis[ j ] > dis[ k ] + mapp[ k ][ j ] ){
				dis[ j ] = dis[ k ] + mapp[ k ][ j ];
			//	vis[ j ] = 1;
			}
		}
	}
		/*for( int i = 0; i <= n; ++i ){
		cout << dis[ i ] << endl;
	}*/
}

int main(){
	while( scanf( "%d", &n ) != EOF ){
		if( !n )
			break;
		scanf( "%d%d", &start, &end );
		for( int i = 0; i <= n; ++i ){
			for( int j = 0;j <= n; ++j ){
				mapp[ i ][ j ] = Max;
			}
		}
		for( int i = 1; i <= n; ++i ){
			scanf( "%d", &num[ i ] );
		}
		for( int i = 1; i <= n; ++i ){
			if( i + num[ i ] <= n ){
				mapp[ i ][ i + num[ i ] ] = 1;
			}
			if( i - num[ i ] >= 1 ){
				mapp[ i ][ i - num[ i ] ] = 1;
			}
		}
		Dijkstra( start );
		if( dis[ end ] == Max )
			puts( "-1" );
		else{
			printf( "%d\n", dis[ end ] );
		}
	}
	return 0;
}






本文转自mfrbuaa博客园博客,原文链接:http://www.cnblogs.com/mfrbuaa/p/5075843.html,如需转载请自行联系原作者


相关文章
|
6月前
Knight Moves(POJ2243)
Knight Moves(POJ2243)
|
机器学习/深度学习
1257:Knight Moves 2021-01-09
1257:Knight Moves 2021-01-09
|
Go
HDOJ/HDU 1087 Super Jumping! Jumping! Jumping!(经典DP~)
HDOJ/HDU 1087 Super Jumping! Jumping! Jumping!(经典DP~)
83 0