题目描述

有一个变量 $x$，初始为 $1$，现在需要经过若干次操作，将 $x$ 变为 $n$。

每次操作可以将 $x$ 变为 $x+1$ 或 $x-1$，新得到的数必须在 $1$ ~ $n$ 的范围内。

特别的，还有 $k$ 个数字 $a_i$。

若当前 $x$ 是 $a_i$ 的倍数，则可以将 $x$ 转化为 $1$ ~ $n$ 范围内任意的 $a_i$ 的倍数。

问将 $x$ 变为 $n$ 的最小操作次数是多少。

---

我的思路是广搜，但是 TLE，代码如下。

#include <algorithm>
#include <cstdio>
#include <queue>
std::queue<int> q;
int n,k,dis[2000001],a[10];
int main() {
	scanf("%d%d",&n,&k);
	std::fill(dis+2,dis+n+1,1000000000);
	for(register int i=0;i<k;i++)
		scanf("%d",a+i);
	q.push(1);
	register int x;
	while(q.size()) {
		x=q.front();
		if(x==n)
			return !printf("%d",dis[x]);
		q.pop();
		if(x>1)
			if(dis[x-1]>dis[x]+1)
				q.push(x-1),
				dis[x-1]=dis[x]+1;
		if(x<n)
			if(dis[x+1]>dis[x]+1)
				q.push(x+1),
				dis[x+1]=dis[x]+1;
		for(register int c,i=0;i<k;i++)
			if(!(x%a[i]))
				for(c=a[i];c<=n;c+=a[i])
					if(dis[c]>dis[x]+1)
						q.push(c),
						dis[c]=dis[x]+1;
	}
	return 0;
}