51nod 1693 水群 （spfa）

Description

总所周知，水群是一件很浪费时间的事，但是其实在水群这件事中，也可以找到一些有意思的东西。

比如现在，bx2k就在研究怎样水表情的问题。

首先，bx2k在对话框中输入了一个表情😏，接下来，他可以进行三种操作。

第一种，是全选复制，把所有表情全选然后复制到剪贴板中。

第二种，是粘贴，把剪贴板中的表情粘贴到对话框中。

第三种，是退格，把对话框中的最后一个表情删去。

假设当前对话框中的表情数是num0，剪贴板中的表情数是num1，那么第一种操作就是num1=num0

第二种操作就是num0+=num1

第三种操作就是num0–

现在bx2k想知道，如果要得到n(1<=n<=10^6)个表情，最少需要几次操作。

请你设计一个程序帮助bx2k水群吧。

Input

一个整数n表示需要得到的表情数

Output

一个整数ans表示最少需要的操作数

Input示例

233

Output示例

17

思路

我们每一次独立的操作无疑就是 复制 1 次 + 粘贴 x 次 + 退格 y 次 ，因为连续复制两次显然无意义，并且退格在粘贴之前与之后都是同样的效果。

于是题目相当于：当前有一个数 $x$ ，操作 $1$ 是 $x=x \times k$ ，代价为 $k$ ；操作 $2$ 是 $x=x-1$ ，代价为 $1$ ，求从 $1$ 到 $n$ 的最小代价。

显然我们可以建图求最短路即为最终的结果，但是 $x=x \times k$ 所生成的边数太多，经过思考我们可以将 $k$ 质因子分解，最终变为 $x=x \times [2,3,5,7…]$ ，这样便消除了其中的冗余边。

经过测试取前 $5$ 个质数就可以保证答案～

AC 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
#define inf 0x7f7f7f7f

int prime[]= {2,3,5,7,11};

bool vis[N];
int dist[N];
int n,maxn;

int spfa(int s,int e)
{
    queue<int> sk;
    maxn = n+10;
    for(int i=0; i<maxn; i++)
    {
        dist[i] = inf;
        vis[i] = false;
    }
    dist[s] = 0;
    vis[s] = true;
    sk.push(s);
    while(!sk.empty())
    {
        int u = sk.front();
        sk.pop();
        vis[u] = false;
        if(u-1>0&&dist[u-1]>dist[u]+1)
        {
            dist[u-1] = dist[u] + 1;
            if(!vis[u-1])
            {
                vis[u-1] = true;
                sk.push(u-1);
            }
        }
        for(int i=0; i<5&&prime[i]*u<maxn; i++)
        {
            int to = prime[i]*u;
            int cost = prime[i];
            if(dist[to]>dist[u]+cost)
            {
                dist[to] = dist[u]+cost;
                if(!vis[to])
                {
                    vis[to]=true;
                    sk.push(to);
                }
            }
        }
    }
    return dist[e];
}


int main()
{
    scanf("%d",&n);
    printf("%d\n",spfa(1,n));
    return 0;
}