解题方法 一般来说有两个方法： 1. 开 bool vis 和 queue a，vis 数组专门储存结果是否已经遍历，a 专门存储每个节点的最短路径大小和值。 2. 开 int dis 数组和 queue a，dis 数组专门存储每个点的最短路径，a 专门存储值。 两种方法时间复杂度相同，第二种似乎更清晰。 代码1（方法一）： 直接使用层数输出（需在中途退出）。 代码2（方法二）： 最后输出 k 节点的最短路径距离（无需中途退出）。

【算法分析】 由于位置的个数很少且要求最小步数，可以考虑从 nnn 位置开始广搜，同时用一个数组 ddd，did_idi 表示从 nnn 位置到 iii 位置需要的步数，最后输出 dkd_kdk 即可。 【参考代码】 【时间复杂度】 O(1e5)O(1e5)O(1e5) 【预计得分】 100pts100pts100pts

这里有模拟的味道...

有个测试样例错了，所以我特判了 有谁知道为什么错吗

不准抄

#include<iostream> #include<queue> using namespace std; int n,k; queue<int>q; int d[100005]; void bfs(int n,int k){ ~~ while(q.size()){~~ ~~ int f=q.front();~~ q.pop(); if(fk){ cout<<d[f]; break; } if(f-1>=0&&d[f-1]-1){ q.push(f-1); d[f-1]=d[f]+1; } if(f+1<=100000&&d[f+1]-1){ q.push(f+1); d[f+1]=d[f]+1; } if(f2<=100000&&d[f2]-1){ q.push(f2); d[f2]=d[f]+1; } } } int main(){ cin>>n>>k; for(int i=1;i<=100000;i++){ d[i]=-1; } q.push(n); d[n]=0; bfs(n,k); return 0; }

增强KRM262，增强MG42，增强Q33！ 题解：

#include <bits/stdc++.h> using namespace std; int n,k; int a[100010]; bool vis[100010]; int main(){ cin>>n>>k; queue<int> q; q.push(n); a[n]=0; vis[n]=true; while(q.size()){ int r=q.front(); q.pop(); if(r==k){ cout<<a[k]<<endl; break; } if(r+1<=100000&&vis[r+1]==false){ q.push(r+1); vis[r+1]=true; a[r+1]=a[r]+1; } if(r-1>=0&&vis[r-1]==false){ q.push(r-1); vis[r-1]=true; a[r-1]=a[r]+1; } if(2r<=100000&&vis[2r]==false){ q.push(2r); vis[2r]=true; a[2*r]=a[r]+1; } } }

#include <bits/stdc++.h> using namespace std; int d[100010],n,k; int main() { cin>>n>>k; for(int i =1;i<=100010;i++){ d[i]=-1; } queue<int> q; q.push(n); d[n]=0; while(q.size()){ int r=q.front(); q.pop(); if(r==k){ cout<<d[k]; break; } if(r>=1 && d[r-1] ==-1){ d[r-1]=d[r]+1; q.push(r-1); } if(r<=100010 && d[r+1] ==-1){ d[r+1]=d[r]+1; q.push(r+1); } if(2r<=100010 && d[r2] ==-1){ d[r2]=d[r]+1; q.push(r2); } } return 0; }

#include <bits/stdc++.h> using namespace std; const int N = 2e5+5; int n,k; int a[N]; void bfs(int x) { queue<int> q; q.push(x); a[x] = 0; while (!q.empty() ) { int r = q.front() ; q.pop(); if(r == k) { cout<<a[k]; return ; }else { if(a[r-1] == 0 && r>=1){ a[r-1] = a[r]+1; q.push(r-1); }if(a[r+1] == 0 && (r+1)<=100000){ a[r+1] = a[r]+1; q.push(r+1); }if(a[2r] == 0 && (2r)<=100000){ a[r2] = a[r]+1; q.push(r2); } } } } int main() { cin>>n>>k; bfs(n); return 0; }