题目大意：给定一个4位素数，一个目标4位素数。每次变换一位，保证变换后依然是素数，求变换到目标素数的最小步数。
解题报告：直接用最短路。
枚举1000-10000所有素数，如果素数A交换一位可以得到素数B，则在AB间加入一条长度为1的双向边。
则题中所求的便是从起点到终点的最短路。使用Dijkstra或SPFA皆可。
当然，纯粹的BFS也是可以的。
用Dijkstra算法A了题目之后，看了一下Discuss，发现了一个新名词，双向BFS。
即从起点和终点同时进行BFS，相遇则求得最短路。
借鉴了思想，自己动手实现了代码。原本以为双向比单向快一倍而已，其实远远不止。
笔者用30W数据分别测试了单向和双向。环境为CodeBlock+MinGW4.7，Debug，双向时间为8.618s，而单向为惊人的139.989s！
简单思考了一下，也还是合理的。单向每次的增长是指数级的，而双向的指数只有单向的一半，优化程度相当高。
好了，贴代码~首先是双向BFS的Dijkstra：
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std; const int maxn=;
int prime[maxn];
const int maxV=;
int first[maxV],vv[maxV*maxV],nxt[maxV*maxV];
int num[maxV];
bool vis[][maxV];
int index; bool check(int a,int b)
{
int k=a-b;
if(k%==)
return true;
if(k< && k%== && a/==b/)
return true;
if(k< && k%== && a/==b/)
return true;
if(a/==b/)
return true;
return false;
} void calPrime()
{
for(int i=;i<maxn;i++) if(!prime[i])
{
for(int j=*i;j<maxn;j+=i)
prime[j]=true;
if(i>= && i<)
{
num[++index]=i;
prime[i]=index;
}
} int e=;
memset(first,,sizeof(first));
for(int i=;i<=index;i++)
for(int j=i+;j<=index;j++) if(check(num[j],num[i]))
{
nxt[e]=first[i],vv[e]=j,first[i]=e++;
nxt[e]=first[j],vv[e]=i,first[j]=e++;
}
} struct Node
{
int node;
int level;
bool operator<(const Node& cmp) const
{
return level>cmp.level;
}
} p,q; int Dijkstra(int sta,int end)
{
if(sta==end)
return ; memset(vis,,sizeof(vis)); sta=prime[sta];
end=prime[end]; priority_queue<Node> pq[];
p.node=sta;
p.level=;
vis[][p.node]=true;
pq[].push(p); p.node=end;
p.level=;
vis[][p.node]=true;
pq[].push(p); for(int i=; !pq[].empty() && !pq[].empty() ;i++)
{
int sel=;
if(pq[].size()>pq[].size())
sel++;
int level=pq[sel].top().level;
while(!pq[sel].empty())
{
p=pq[sel].top();
if(p.level!=level) //先判断，否则会pop掉丢失情况
break;
pq[sel].pop(); for(int e=first[p.node];e;e=nxt[e])
{
if(vis[-sel][vv[e]])
return i+;
if(!vis[sel][vv[e]])
{
q.level=p.level+;
q.node=vv[e];
vis[sel][vv[e]]=true;
pq[sel].push(q);
}
}
}
} return -;
} int main()
{
calPrime(); int T;
scanf("%d",&T);
while(T--)
{
int sta,end;
scanf("%d%d",&sta,&end);
int ans=Dijkstra(sta,end);
if(ans==-)
printf("Impossible\n");
else
printf("%d\n",ans);
}
}
然后是单向的BFS+Dijkstra：
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std; const int maxn=;
int prime[maxn];
const int maxV=;
int first[maxV],vv[maxV*maxV],nxt[maxV*maxV];
int num[maxV];
bool vis[maxV];
int index;
int count; bool check(int a,int b)
{
int k=a-b;
if(k%==)
return true;
if(k< && k%== && a/==b/)
return true;
if(k< && k%== && a/==b/)
return true;
if(a/==b/)
return true;
return false;
} void calPrime()
{
for(int i=;i<maxn;i++) if(!prime[i])
{
for(int j=*i;j<maxn;j+=i)
prime[j]=true;
if(i>= && i<)
{
num[++index]=i;
prime[i]=index;
}
} int e=;
memset(first,,sizeof(first));
for(int i=;i<=index;i++)
for(int j=i+;j<=index;j++) if(check(num[j],num[i]))
{
nxt[e]=first[i],vv[e]=j,first[i]=e++;
nxt[e]=first[j],vv[e]=i,first[j]=e++;
}
} struct Node
{
int k;
int w;
bool operator<(const Node& cmp) const
{
return w>cmp.w;
}
} p,q; int Dijkstra(int sta,int end)
{
memset(vis,,sizeof(vis));
end=prime[end]; p.k=prime[sta];
p.w=;
vis[p.k]=true; priority_queue<Node> pq;
pq.push(p); while(!pq.empty())
{
p=pq.top();
pq.pop(); if(p.k==end)
return p.w; for(int e=first[p.k];e;e=nxt[e]) if(!vis[vv[e]])
{
q.k=vv[e];
q.w=p.w+;
vis[q.k]=true;
pq.push(q);
}
}
return -;
} int main()
{
calPrime(); int T;
scanf("%d",&T);
while(T--)
{
int sta,end;
scanf("%d%d",&sta,&end);
int ans=Dijkstra(sta,end);
if(ans==-)
printf("Impossible\n");
else
printf("%d\n",ans);
}
}
测试数据我放在了百度云，有兴趣可以下载下来试一下：http://pan.baidu.com/share/link?shareid=4217669741&uk=2804348991