首页 > 代码库 > hdu1548 A strange lift(bfs 或Dijkstra最短路径)
hdu1548 A strange lift(bfs 或Dijkstra最短路径)
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #define M 205 6 #define INF 0x3f3f3f3f 7 using namespace std; 8 9 int map[M][M];10 int d[M], vis[M];11 int n;12 int b, e;13 14 void Dijkstra(){15 memset(d, 0x3f, sizeof(d));16 memset(vis, 0, sizeof(vis));17 d[b]=0;18 vis[b]=1;19 int root=b;20 for(int j=1; j<n; ++j){21 int minLen=INF, p; 22 for(int i=1; i<=n; ++i){23 if(!vis[i] && d[i] > d[root] + map[root][i])24 d[i] = d[root] + map[root][i]; 25 if(!vis[i] && minLen>d[i]){26 p=i;27 minLen=d[i]; 28 }29 }30 if(minLen==INF)31 return;32 root=p;33 vis[root]=1;34 } 35 }36 37 int main(){38 while(cin>>n && n){39 cin>>b>>e;40 memset(map, 0x3f, sizeof(map));41 for(int i=1; i<=n; ++i){42 int x, xx;43 cin>>x;44 map[i][i]=0;// i+(-)x 表示 从第i层可以到达第 i+(-)x层 45 xx=i-x;46 if(xx>=1) map[i][xx]=1;47 xx=i+x;48 if(xx<=n) map[i][xx]=1; 49 } 50 Dijkstra();51 if(d[e]==INF)52 cout<<"-1"<<endl;53 else54 cout<<d[e]<<endl;55 }56 return 0;57 }
1 /* 2 思路:当前电梯位置的两个方向进行搜索! 3 注意:搜索时的界限, 用x表示将要到达的电梯的位置 4 1. 首先是x>=1 5 2. x<=n 6 3. vis[x]!=0 表明bfs时候没有经过这个楼层 7 */ 8 #include<iostream> 9 #include<cstring>10 #include<cstdio>11 #include<queue> 12 using namespace std;13 struct node{14 int x;15 int step; 16 node(){}17 node(int x, int step){18 this->x=x;19 this->step=step; 20 }21 };22 queue<node>q;23 int n, b, e;24 int f[205];25 int vis[205];26 27 bool bfs(){28 while(!q.empty()) q.pop();29 memset(vis, 0, sizeof(vis)); 30 q.push(node(b,0));31 vis[b]=1;32 while(!q.empty()){33 node cur=q.front();34 q.pop();35 if(cur.x==e){36 cout<<cur.step<<endl;37 return true; 38 } 39 int xx;40 xx=cur.x+f[cur.x];41 if(xx==e){42 cout<<cur.step+1<<endl;43 return true;44 }45 if(xx<=n && !vis[xx]){46 q.push(node(xx, cur.step+1));47 vis[xx]=1;48 }49 xx=cur.x-f[cur.x];50 if(xx==e){51 cout<<cur.step+1<<endl;52 return true;53 }54 if(xx>=1 && !vis[xx]){55 q.push(node(xx, cur.step+1));56 vis[xx]=1;57 }58 }59 return false;60 }61 62 int main(){63 while(cin>>n && n){64 cin>>b>>e;65 for(int i=1; i<=n; ++i)66 cin>>f[i];67 if(!bfs())68 cout<<"-1"<<endl; 69 }70 return 0; 71 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。