hdu 1548 A strange lift 宽搜bfs+优先队列

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<cmath>
 6 #include<algorithm>
 7 #include<queue>
 8 #define inf 0x7fffffff
 9 using namespace std;
10 const int maxn=200+10;
11 const int M = 40000+10;
12 
13 int n,A,B;
14 int an[maxn];
15 struct node
16 {
17     int cnt,id;
18     int value;
19     friend bool operator < (node a,node b)
20     {
21         return a.cnt > b.cnt;
22     }
23 }cur,tail;
24 
25 int vis[maxn];
26 int bfs()
27 {
28     priority_queue<node> Q;
29     cur.id=A ;cur.cnt=0 ;
30     cur.value=an[A];
31     Q.push(cur);
32     memset(vis,0,sizeof(vis));
33     vis[A]=1;
34     int count=0;
35     while (!Q.empty())
36     {
37         cur=Q.top() ;Q.pop() ;
38         if (cur.id==B) return cur.cnt;
39 
40         //cout<<cur.id<<" "<<an[cur.id]<<" "<<cur.cnt<<endl;
41         tail.id=cur.id+an[cur.id];
42         if (tail.id>=1 && tail.id<=n && !vis[tail.id])
43         {
44             tail.value=an[tail.id];
45             tail.cnt=cur.cnt+1;
46             vis[tail.id]=1;
47             Q.push(tail);
48         }
49 
50         tail.id=cur.id-an[cur.id];
51         if (tail.id>=1 && tail.id<=n && !vis[tail.id])
52         {
53             tail.value=an[tail.id];
54             tail.cnt=cur.cnt+1;
55             vis[tail.id]=1;
56             Q.push(tail);
57         }
58     }
59     return -1;
60 }
61 
62 int main()
63 {
64     while (scanf("%d",&n)!=EOF && n)
65     {
66         scanf("%d%d",&A,&B);
67         for (int i=1 ;i<=n ;i++) scanf("%d",&an[i]);
68         printf("%d\n",bfs());
69     }
70     return 0;
71 }