POJ 3126 Prime Path 素数筛,bfs

时间:2021-07-11 18:55:43

题目: http://poj.org/problem?id=3126

困得不行了,没想到敲完一遍直接就A了,16ms,debug环节都没进行。人品啊。

 #include <stdio.h>
#include <string.h>
#include <queue>
using namespace std; bool prime[];
int vis[];
int s, t; void prime_init()
{
memset(prime, , sizeof(prime));
prime[] = ;
for(int i = ; i < ; i += )
prime[i] = ;
for(int i = ; i < ; i += )
{
if(prime[i])
{
for(int j = i*i; j < ; j += i+i)
prime[j] = ;
}
}
} queue<int>q;
void bfs()
{
while(!q.empty())q.pop();
memset(vis, , sizeof(vis));
q.push(s);
vis[s] = ;
while(!q.empty())
{
int u = q.front();
q.pop();
if(u == t)
{
printf("%d\n", vis[u]-);
return;
}
int a = u % ;
int b = u % - a;
int c = u % - a - b;
int d = u - u % ;
for(int i = u-a; i <= u-a+; i++)
{
if(prime[i] && !vis[i])
{
q.push(i);
vis[i] = vis[u] + ;
}
}
for(int i = u-b; i <= u-b+; i += )
{
if(prime[i] && !vis[i])
{
q.push(i);
vis[i] = vis[u] + ;
}
}
for(int i = u-c; i <= u-c+; i += )
{
if(prime[i] && !vis[i])
{
q.push(i);
vis[i] = vis[u] + ;
}
}
for(int i = u-d+; i <= u-b+; i += )
{
if(prime[i] && !vis[i])
{
q.push(i);
vis[i] = vis[u] + ;
}
}
}
} int main()
{
prime_init();
int n;
scanf("%d", &n);
while(n--)
{
scanf("%d %d", &s, &t);
bfs();
}
return ;
}