PrimePath[POJ3126][SPFA/BFS]

  • Z时代
  • 2024-01-10
  • 分类：综合

coding

描述

孤单的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
19usingnamespace std;
20int n,m,cnt,ct;
21int isp[maxn],p[maxn],head[maxn],dis[maxn],vis[maxn],id[maxn];
22struct E{
23int v,next;
24}e[maxm];
25 inline int read()
26{
27int x=0,f=1;char c=getchar();
28while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
29while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
30return x*f;
31}
32
33 inline int judge(int x,int y)
34{
35int sum=0;
36while(x)    {if(x%10!=y%10)    sum++;x/=10,y/=10;}
37return sum==1;
38}
39
40void pre()
41{
42     rep(i,2,lim)
43    {
44if(!isp[i])    p[++cnt]=i,id[i]=cnt;
45for(RG j=1;j<=cnt&&p[j]*i<=lim;j++)
46        {
47             isp[i*p[j]]=1;
48if(!(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
54int 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;
59while(!que.empty())
60    {
61         u=que.front(),que.pop(),vis[u]=0;
62for(RG i=head[u];i;i=e[i].next)
63        {
64             v=e[i].v;
65if(dis[v]>dis[u]+1){
66                 dis[v]=dis[u]+1;
67if(!vis[v])    vis[v]=1,que.push(v);
68            }
69        }
70    }
71return dis[T];
72}
73
74int main()
75{
76int Tim=read();
77    pre();
78while(Tim--)
79    {
80         scanf("%d%d",&n,&m);
81         printf("%d\n",SPFA(id[n],id[m]));
82    }
83return0;
84 }

View Code

以上是 PrimePath[POJ3126][SPFA/BFS] 的全部内容， 来源链接： utcz.com/z/509956.html

回到顶部