http://poj.org/problem?id=3126這里兩天寫(xiě)bfs寫(xiě)了不少了，慢慢有點(diǎn)感覺(jué)啦，哈哈，隊(duì)列是個(gè)好東西。從SPFA的FIFO隊(duì)列到堆實(shí)現(xiàn)的優(yōu)先級(jí)隊(duì)列，應(yīng)該還有還多好多吧。。。。慢慢去了解！
跟隊(duì)友討論了討論，1000的節(jié)點(diǎn)覺(jué)得這個(gè)圖大了點(diǎn)如果Floyd地話，肯定超時(shí)！想想也用不找最短路嘛，這里路徑權(quán)重都是1，所以bfs啊，肯定最短路咯。
不過(guò)，寫(xiě)了一種方法，肯定是還有其他方法的。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，很爽啊！！哈哈，