题意:有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,如需转载请自行联系原作者