ZR#1012

## ZR#1012

blog咕咕咕了好久，开始补。

解法：

一个很显然的性质， $ x $ 只能转移到 $ x+1 $ 或者 $ 2x $ 处，所以我们可以以此性质建图，即 $ x $ 向 $ x + 1 $ 和 $ 2x $ 处连边，然后跑一遍SPFA就行了，建图过程详见代码。

CODE:

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<queue>

using namespace std;

#define INF 2147483647

const int N = 1e6 + 100;

int dis[N],x,n;

bool vis[N];

queue<int> q;

inline void calc(int v,int u,int val) {

	if(dis[v] > dis[u] + val) {

		dis[v] = dis[u] + val;

		if(!vis[v]) q.push(v),vis[v] = true;

	}

}

inline void spfa() {

	while(!q.empty()) {

		int v = q.front();

        q.pop();

		if(v < n) calc(v + 1,v,1);

		if(v > 0) {

			calc(v - 1,v,1);

			for(int i = 1 ; v * i <= n ; i++) {

				if(v * (i + 1) > n) calc(n,v,2 * i + 4 + v * (i + 1) - n);

				else calc(v * (i + 1),v,2 * i + 4);

			}

		}

		vis[v] = false;

	}

}

int main() {

    scanf("%d%d",&x,&n);

    for(int i = 0 ; i <= n ; i++) dis[i] = INF;

	if(x > n) {

		dis[0] = 3,dis[n] = x - n;

		vis[x] = vis[n] = vis[0] = true;

		q.push(0);

        q.push(n);

	} else {

		dis[x] = 0;

        vis[x] = 1;

		q.push(x);

	}

	spfa();

	printf("%d\n",dis[n]);

    //system("pause");

	return 0;

}

巴特西

ZR#1012

## ZR#1012

解法：

CODE:

最新文章

热门文章