# 官方题解｜欢乐赛#41 T5

T5.最短路径

题目思路

本题是很经典的广搜问题，我们开一个dist数组，dist[i]表示从a到i的最短路径，一开始初始化为无穷大。每个数值只遍历一次，在广搜的时候通过dist[i]的值来判断是否这个点已经搜过。如果通过操作得到的数值是在合法的范围内且没被搜过就把这个数值加入队列，并继续搜，一直搜到$b$为止。

参考代码

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

const int N = 10010;
int dist[N];

void solve(){
    int a, b;
    cin >> a >> b;
    queue<int>q;
    q.push(a);
    //将dist数组初始化为无穷大
    memset(dist, 0x3f, sizeof dist);
    //起点到起点的距离为0
    dist[a] = 0;
    while(q.size()){
        int x = q.front();
        q.pop();
        if(x * 2 <= 10000 && dist[x * 2] > 1e9){//操作1
            dist[x * 2] =  dist[x] + 1;
            q.push(x * 2);
        }
        if(x - 1 >= 0 && dist[x - 1] > 1e9){//操作2
            dist[x - 1] = dist[x] + 1;
            q.push(x - 1);
        }
    }
    cout << dist[b] << endl; 
}
int main(){
    int t;
    cin >> t;
    while(t -- ){
        solve();
    }
}