#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;
}

• Re:优不优先队列都能AC,不过注意下两个相等的情况。WA了无数次才发现 (1213) 3096947160 2022-03-12 12:18:37