| ||||||||||
| 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