http://poj.org/problem?id=3126这里两天写bfs写了不少了，慢慢有点感觉啦，哈哈，队列是个好东西。从SPFA的FIFO队列到堆实现的优先级队列，应该还有还多好多吧。。。。慢慢去了解！
跟队友讨论了讨论，1000的节点觉得这个图大了点如果Floyd地话，肯定超时！想想也用不找最短路嘛，这里路径权重都是1，所以bfs啊，肯定最短路咯。
不过，写了一种方法，肯定是还有其他方法的。baidu去看看
#include<stdio.h>
#include<string.h>
#include<math.h>
int prime[1200],f[10005],map[1200][1200];
int que[1200],d[1200];
int a,b,tot;
int bfs()
{
int head,tail,now,i,s,t;
if (a==b)
return 0;
memset(d,0,sizeof(d));
s=f[a];
t=f[b];
head=0;
tail=1;
que[1]=s;
d[s]=1;
while (head<tail)
{
head++;
now=que[head];
for (i=1; i<=tot ; i++ )
if (!d[i]&&map[now][i]==1)
{
if (i==t)
return d[now];
tail++;
que[tail]=i;d[i]=d[now]+1;
}
}
}
int link(int s,int t)
{
int i;
i=0;
if (s/1000!=t/1000)
i++;
if ((s%1000)/100!=(t%1000)/100)
i++;
if ((s%100)/10!=(t%100)/10)
i++;
if (s%10!=t%10)
i++;
return i;
}
int init()
{
int i,j,k;
memset(f,0,sizeof(f));
tot=0;
i=2;k=1;
while (i<=10000)
{
while (f[i]) i++;
j=i;
while (j<=10000)
f[j]=1,j+=i;
if (i>1000)
f[i]=++tot,prime[tot]=i;
}
tot--;
for (i=1; i<=tot ; i++ )
for (j=1; j<=i ; j++ )
map[i][j]=map[j][i]=link(prime[i],prime[j]);
}
int main()
{
int n,ans;
init();
scanf("%d",&n);
while (n>0)
{
n--;
scanf("%d%d",&a,&b);
ans=bfs();
printf("%d\n",ans);
}
return 0;
}
嗯，一次AC，很爽啊！！哈哈，