本文共 1632 字，大约阅读时间需要 5 分钟。
题意：有n层楼层，如今在每一层有两个button，分别为up和down，按动button时，能够向上或向下跳动num[ i ]层；问是否能以最少的次数从A到B层，不能输出-1；
解析：构图，将从i层到按动button后跳转的楼层。看作连通状态，赋值为1，这样就转换成单源最短路问题；
#include#include #include 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，如需转载请自行联系原作者