Prime Path[POJ3126] [SPFA/BFS]

描述

孤单的zydsg又一次孤单的度过了520，不过下一次不会再这样了。zydsg要做些改变，他想去和素数小姐姐约会。
所有的路口都被标号为了一个4位素数，zydsg现在的位置和素数小姐姐的家也是这样，如果两个路口间只差1个数字，则有一条路连通两个路口。（例如1033和1073间有一条路连接）
现在，你知道了zydsg的位置和素数小姐姐的家，问最少zydsg要走多少条路才能见到素数小姐姐。例如：如果zydsg在1033，素数小姐姐的家在8179，最少要走6条街，走法为：

1033
1733
3733
3739
3779
8779
8179

Input

输入数据有多组，首先是一个数字n，代表之后有n组数据。 其次，在每一组输入中，都包含两个数字a和b，代表zydsg的位置和素数小姐姐家的位置。 其中，a和b都是四位数，而且不含前导0。

Output

每组输入输出一行，表示zydsg最少需要走多少条路。若不存在合法的路径，则输出单词“Impossible”。Sample Input

3
1033 8179
1373 8017
1033 1033

Sample Output

6
7
0

分析

首先我们要筛素数，接下来

方法一：

两个“相邻的”素数连边，每次从开头向终点跑SPFA

方法二：

按个十百千位向四周扩散，BFS

代码（SPFA）

 

 1 #include<set>
 2 #include<map>
 3 #include<queue>
 4 #include<stack>
 5 #include<cmath>
 6 #include<cstdio>
 7 #include<cstring>
 8 #include<iostream>
 9 #include<algorithm>
10 #define RG register int
11 #define rep(i,a,b)    for(RG i=a;i<=b;++i)
12 #define per(i,a,b)    for(RG i=a;i>=b;--i)
13 #define ll long long
14 #define inf (1<<29)
15 #define maxn 10005
16 #define lim 10002
17 #define maxm 1500005
18 #define add(x,y) e[++ct]=(E){y,head[x]},head[x]=ct
19 using namespace std;
20 int n,m,cnt,ct;
21 int isp[maxn],p[maxn],head[maxn],dis[maxn],vis[maxn],id[maxn];
22 struct E{
23     int v,next;
24 }e[maxm];
25 inline int read()
26 {
27     int x=0,f=1;char c=getchar();
28     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
29     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
30     return x*f;
31 }
32 
33 inline int judge(int x,int y)
34 {
35     int sum=0;
36     while(x)    {if(x%10!=y%10)    sum++;x/=10,y/=10;}
37     return sum==1;
38 }
39 
40 void pre()
41 {
42     rep(i,2,lim)
43     {
44         if(!isp[i])    p[++cnt]=i,id[i]=cnt;
45         for(RG j=1;j<=cnt&&p[j]*i<=lim;j++)
46         {
47             isp[i*p[j]]=1;
48             if(!(i%p[j]))    break;
49         }
50     }
51     rep(i,169,cnt)    rep(j,i+1,cnt)    if(judge(p[i],p[j])) add(i,j),add(j,i);
52 }
53 
54 int SPFA(int S,int T)
55 {
56     memset(dis,63,sizeof(dis));dis[S]=0;
57     queue<int> que;que.push(S);
58     RG u,v;
59     while(!que.empty())
60     {
61         u=que.front(),que.pop(),vis[u]=0;
62         for(RG i=head[u];i;i=e[i].next)
63         {
64             v=e[i].v;
65             if(dis[v]>dis[u]+1){
66                 dis[v]=dis[u]+1;
67                 if(!vis[v])    vis[v]=1,que.push(v);
68             }
69         }
70     }
71     return dis[T];
72 }
73 
74 int main()
75 {
76     int Tim=read();
77     pre();
78     while(Tim--)
79     {
80         scanf("%d%d",&n,&m);
81         printf("%d\n",SPFA(id[n],id[m]));
82     }
83     return 0;
84 }

View Code