51nod 1693 水群（神奇的最短路！）

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1693

题意：

思路：

这个思路真是神了。。

对于每个点$i$，它需要和$i-1$连一条边，代表退格操作，权值为1，但是对于复制粘贴操作就比较麻烦了，因为它可以复制之后粘贴多次，这样的话，就可以从$i$转换成$i*k$，k就是操作的次数，但是k的取值太多了，我们肯定是需要优化的（毕竟就0.4秒的时间。。），首先k的取值可能限制在质数之内，为什么可以把合数去掉呢，因为它完全可以由多次代价低的操作组合在一起实现等价的效果，代价总和还是一样的。进一步可以发现k的范围大致就是{2,3,5,7,11,13}这几个数之间（这我也不太清楚为什么，我觉得是如果一下子粘贴那么多次，那它完全可以先粘贴后然后复制再粘贴，这样的话代价会更小一点），还有就是退格操作不会连续超过4次（这我也不太清楚，我觉得是如果退格次数多了，那完全可以在复制前先退格然后再复制粘贴）。

总之，就感觉这道题目很神，学习了。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<vector>
 6 #include<stack>
 7 #include<queue>
 8 #include<cmath>
 9 #include<map>
10 #include<set>
11 using namespace std;
12 typedef long long ll;
13 const int INF = 0x3f3f3f3f;
14 const int maxn=1e6+5;
15 
16 int n;
17 int d[maxn];
18 bool inq[maxn];
19 int prime[]={2,3,5,7,11,13};
20 
21 void spfa()
22 {
23     memset(d,0x3f,sizeof(d));
24     memset(inq,0,sizeof(inq));
25     queue<int> Q;
26     Q.push(1);
27     d[1]=0;
28     inq[1]=1;
29     while(!Q.empty())
30     {
31         int u=Q.front(); Q.pop(); inq[u]=0;
32         for(int i=0;i<6 && prime[i]*u<n+5;i++)
33         {
34             int v=prime[i]*u;
35             if(d[v]>d[u]+prime[i])
36             {
37                 d[v]=d[u]+prime[i];
38                 if(!inq[v])  {inq[v]=1;Q.push(v);}
39             }
40         }
41         int v=u-1;
42         if(d[v]>d[u]+1)
43         {
44             d[v]=d[u]+1;
45             if(!inq[v])  {inq[v]=1;Q.push(v);}
46         }
47     }
48     printf("%d
",d[n]);
49 }
50 
51 int main()
52 {
53     //freopen("in.txt","r",stdin);
54     scanf("%d",&n);
55     spfa();
56     return 0;
57 }