Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:优不优先队列都能AC,不过注意下两个相等的情况。WA了无数次才发现In Reply To:优不优先队列都能AC,不过注意下两个相等的情况。WA了无数次才发现 Posted by:qq1250173534 at 2020-03-01 19:50:27 > #include <iostream> > #include <cstring> > #include <cstdio> > #include <algorithm> > #include <queue> > #include <cmath> > using namespace std; > const int maxn = 1e5+10; > struct node{ > int x; //当前点的坐标 > int t; //时间 > bool operator <(const node s)const{ > return s.t < t; > } > }; > priority_queue<node>q; > bool visited[maxn]; > void bfs(int k) > { > while(!q.empty()){ > node p = q.top(),ptr; > q.pop(); > if(p.x == k){ > printf("0\n"); > return ; > } > for(int i = 0;i < 3;i++){ > if(i == 0){ > ptr.x = p.x + 1; > } > if(i == 1){ > ptr.x = p.x - 1; > } > if(i == 2){ > ptr.x = p.x * 2; > } > if(ptr.x < 0 || ptr.x > maxn || visited[ptr.x] == true){ > continue; > } > ptr.t = p.t + 1; > if(ptr.x == k){ > printf("%d\n",ptr.t); > return ; > } > visited[ptr.x] = true; > q.push(ptr); > } > } > } > int main() > { > int n,k; > while(~scanf("%d%d",&n,&k)){ > memset(visited,false,sizeof(visited)); > while(!q.empty()){ > q.pop(); > } > node p; > p.x = n;p.t = 0; > q.push(p); > visited[n] = true; > bfs(k); > } > return 0; > } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator