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

Sample Output

分析

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

方法一：

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

方法二：

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

代码（SPFA）

 #include<set>

 #include<map>

 #include<queue>

 #include<stack>

 #include<cmath>

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #define RG register int

 #define rep(i,a,b)    for(RG i=a;i<=b;++i)

 #define per(i,a,b)    for(RG i=a;i>=b;--i)

 #define ll long long

 #define inf (1<<29)

 #define maxn 10005

 #define lim 10002

 #define maxm 1500005

 #define add(x,y) e[++ct]=(E){y,head[x]},head[x]=ct

 using namespace std;

 int n,m,cnt,ct;

 int isp[maxn],p[maxn],head[maxn],dis[maxn],vis[maxn],id[maxn];

 struct E{

     int v,next;

 }e[maxm];

 inline int read()

 {

     int x=,f=;char c=getchar();

     while(c<''||c>''){if(c=='-')f=-;c=getchar();}

     while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

     return x*f;

 }

 inline int judge(int x,int y)

 {

     int sum=;

     while(x)    {if(x%!=y%)    sum++;x/=,y/=;}

     return sum==;

 }

 void pre()

 {

     rep(i,,lim)

     {

         if(!isp[i])    p[++cnt]=i,id[i]=cnt;

         for(RG j=;j<=cnt&&p[j]*i<=lim;j++)

         {

             isp[i*p[j]]=;

             if(!(i%p[j]))    break;

         }

     }

     rep(i,,cnt)    rep(j,i+,cnt)    if(judge(p[i],p[j])) add(i,j),add(j,i);

 }

 int SPFA(int S,int T)

 {

     memset(dis,,sizeof(dis));dis[S]=;

     queue<int> que;que.push(S);

     RG u,v;

     while(!que.empty())

     {

         u=que.front(),que.pop(),vis[u]=;

         for(RG i=head[u];i;i=e[i].next)

         {

             v=e[i].v;

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

                 dis[v]=dis[u]+;

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

             }

         }

     }

     return dis[T];

 }

 int main()

 {

     int Tim=read();

     pre();

     while(Tim--)

     {

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

         printf("%d\n",SPFA(id[n],id[m]));

     }

     return ;

 }

巴特西

Prime Path[POJ3126] [SPFA/BFS]

最新文章

热门文章