Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 素数筛+BFS AC代码丑的一批供大家参考

Posted by xsjlmzs at 2018-08-07 13:20:47 on Problem 3126
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#include<utility>
using namespace std;
const int MAXN=1e4+1;
typedef pair<int,int> P;
bool is_prime[MAXN];
int prime[MAXN];
bool vis[MAXN];
int p=0;
int arr1[4];//临时存放各位
int arr2[4];//临时存放各位
vector<int>G[MAXN];
bool check(int i,int j)//是否连通
{
int cnt=0;
int a=prime[i];
int b=prime[j];
while(a)
{
arr1[cnt++]=a%10;
a/=10;
}
cnt=0;
while(b)
{
arr2[cnt++]=b%10;
b/=10;
}
cnt=0;
for(int i=0;i<4;++i)
{
if(arr1[i]-arr2[i]!=0)
cnt++;
}
if(cnt>1) return false;
else return true;
}
void sieve()//素数筛
{
for(int i=0;i<MAXN;++i)
{
is_prime[i]=true;
}
is_prime[0]=is_prime[1]=false;
for(int i=2;i<MAXN;++i)
{
if(is_prime[i])
{
if(i>1000)
prime[p++]=i;
for(int j=2*i;j<MAXN;j+=i)
{
is_prime[j]=false;
}
}
}
}
void make_graph()//建图
{
for(int i=0;i<p;++i)
{
for(int j=i+1;j<p;++j)
{
if(check(i,j))
{
G[i].push_back(j);
G[j].push_back(i);
}
}
}
}
int BFS(int x,int y)
{
int minn=1<<30;
queue<P>que;
que.push(P(x,0));
while(!que.empty())
{
P tmp=que.front();
que.pop();
int u=tmp.first;
int s=tmp.second;
if(u==y)
{
minn=min(minn,s);
}
for(int i=0;i<G[u].size();++i)
{
int v=G[u][i];
if(!vis[v])
{
vis[v]=true;
que.push(P(v,s+1));
}
}
}
return minn;
}
int main()
{
int T;
scanf("%d",&T);
sieve();
make_graph();
while(T--)
{
memset(vis,0,sizeof(vis));
int st,ed;
scanf("%d%d",&st,&ed);
st=lower_bound(prime,prime+p,st)-prime;
ed=lower_bound(prime,prime+p,ed)-prime;
if(ed==p)//非素数时
printf("Impossible\n");
else
{
int ans=BFS(st,ed);
if(ans==(1<<30))
printf("Impossible\n");
else
printf("%d\n",ans);
}
}
return 0;
}

Followed by: