Prime Path[POJ3126] [SPFA/BFS]-白红宇

Prime Path[POJ3126] [SPFA/BFS]

阅读量：4948 次

发布时间：2019-06-11

本文共 2285 字，大约阅读时间需要 7 分钟。

描述

孤单的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

31033 81791373 80171033 1033

Sample Output

分析

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

方法一：

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

方法二：

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

代码（SPFA）

1 #include
      
        2 #include
        3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
             
               9 #include
              
               10 #define RG register int11 #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 long14 #define inf (1<<29)15 #define maxn 1000516 #define lim 1000217 #define maxm 150000518 #define add(x,y) e[++ct]=(E){y,head[x]},head[x]=ct19 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
               
                 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

转载于:https://www.cnblogs.com/ibilllee/p/9244052.html

你可能感兴趣的文章