题解

解题方法

一般来说有两个方法：

1. 开 bool vis 和 queue a，vis 数组专门储存结果是否已经遍历，a 专门存储每个节点的最短路径大小和值。

2. 开 int dis 数组和 queue a，dis 数组专门存储每个点的最短路径，a 专门存储值。

两种方法时间复杂度相同，第二种似乎更清晰。

代码1（方法一）：

#include<bits/stdc++.h>
using namespace std;

struct P{
    int ce; //当前遍历层数（最短路径大小）
    int z; //节点值
};

const int N=2e5+5;
int n,k;
bool vis[N]; //用变量记载是否访问过
queue<P> a; //以结构体为类型的队列

bool check(int x){
    if(x>=0&&x<=k*2&&vis[x]==0) return true;
    return false;
}

int main(){
    cin>>n>>k;

    vis[n]=1; //已访问
    a.push({0,n}); //当前层数：0。当前值：n

    while(!a.empty()){
        P x=a.front();
        a.pop();

        if(x.z==k){ //如果找到目标节点
            cout<<x.ce; //输出当前层数（最短路径）
            return 0;
        }

        int u[]={x.z+1,x.z-1,2*x.z}; 

        for(int i=0;i<=2;i++){
            if(check(u[i])){
                vis[u[i]]=1; //标记
                a.push({x.ce+1,u[i]}); //放入队列（层数+1）
            }
        }
    }

    return 0;
}

直接使用层数输出（需在中途退出）。

代码2（方法二）：

#include<bits/stdc++.h>
using namespace std;

const int N=2e5;
int n,k,dis[N+10]; //dis数组到记录点i的最短路径
queue<int> a;

bool check(int x){
	if(x>=0&&x<=2*k&&dis[x]==0){
		return true;
	}
	return false;
}

int main(){
	cin>>n>>k;
	
	fill(dis+1,dis+N+5,-1);
	dis[n]=0;
	a.push(n); //放入队列

	while(!a.empty()){
		int now=a.front();
		a.pop();
		int u[]={now+1,now-1,now*2}; //3个now的“子节点”（有点抽象的子节点）
		
		for(int i=0;i<=2;i++){
			if(check(u[i])){ //如果符合要求
				dis[u[i]]=dis[now]+1; //继承，很明显当前的节点是now的下一层，所以路径长度+1
				a.push(u[i]); //放入队列
			}
		}
	}
	
	cout<<dis[k]; //直接输出第k个节点的最短路径距离
	
	return 0;
} 

最后输出 k 节点的最短路径距离（无需中途退出）。