http://poj.org/problem?

id=3126

题目大意：

给你两个四位的素数s和t，要求每次改变一个数字。使得改变后的数字也为素数，求s变化到t的最少变化次数。

思路：

首先求出全部4位素数。

对于两个素数之间，假设仅仅相差一个数字，那么就建立图。（双向）

最后求最短路就可以（能够SPFA也能够BFS）

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int MAXN=10000+10;const int INF=0x3ffffff;bool isprimer[MAXN];int primer[MAXN],num;int head[MAXN],len;struct edge{	int to,next;	}e[MAXN*10];void add(int from,int to){	e[len].to=to;	e[len].next=head[from];	head[from]=len++;}//推断两个数仅有一个数字不同 bool judge(char *x,char *y){	int cnt=0;	for(int i=0;i<4;i++)		if(x[i]==y[i])		  cnt++;	return cnt==3;}int dis[MAXN];bool vis[MAXN];int spfa(int s,int t){		for(int i=1000;i<=10000;i++)		{			dis[i]=INF;			vis[i]=0;		}			dis[s]=0;		vis[s]=true;		queue
         
           q;		q.push(s);		while(!q.empty())		{			int cur=q.front();			q.pop();			for(int i=head[cur];i!=-1;i=e[i].next)			{				int to=e[i].to;				if(dis[cur]+ 1 < dis[to])				{					dis[to]=dis[cur]+1;					if(!vis[to])						q.push(to);				}			}		}		return dis[t];}int main(){	memset(head,-1,sizeof(head));	num=len=0;			for(int i=2;i*i