hdu 5945 BFS + 剪枝

看大部分题解写的是单调队列+DP，那我就多贴一个BFS的吧

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<queue>
using namespace std;

int d[1000100];
bool f[1000100];
int T,x,y,t,k;

void BFS()
{
    queue<int>q;
    d[x] = 0;
    q.push(x);
    f[x] = 1;
    while(!q.empty())
    {
        int t = q.front();
        q.pop();
        if(t == 1)
        {
            printf("%d\n",d[1]);
            return;
        }
        if(t % k == 0 && f[t / k] == 0)
        {
            d[t / k] = min(d[t / k],d[t] + 1);
            if(t / k == 1)
            {
                printf("%d\n",d[t] + 1);
                return;
            }
            q.push(t / k);
            f[t / k] = 1;
        }
        if(t - y <= 1)    //一定能由t再加1步得到1
        {
            printf("%d\n",d[t] + 1);
            return;
        }
        for(int i = y;i >= 1; --i)
        {
            if(t <= i) break;
            if(f[t - i] == 0)
            {
                d[t - i] = d[t] + 1;
                q.push(t - i);
                f[t - i] = 1;
            }
            else break;   //已经入过队不需要再次遍历了
        }
    }
}

int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&x,&k,&y);
        memset(f,0,sizeof(f));
        memset(d,0x3f,sizeof(d));
        BFS();
    }
    return 0;
}