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

## Re:原来auto有毒！

Posted by 20051106 at 2016-12-13 21:21:03 on Problem 3126
In Reply To:原来auto有毒！ Posted by:20051106 at 2016-12-11 21:52:06
> 原先程序：
> #include<iostream>
> #include<cstdio>
> #include<vector>
> #include<cmath>
> #include<algorithm>
> #include<string>
> #include<set>
> #include<map>
> #include<ctime>
> #include<cstring>
> #include<cassert>
> #include<bitset>
> #include<sstream>
> #include<queue>
> using namespace std;
> int prime[10100],d[10100];
> vector<int>a[10100],primes;
> int isValid(int x,int y)
> {
> 	int dif=0;
> 	for(int i=0;i<4;i++)
> 	{
> 		dif+=(x%10!=y%10);
> 		x/=10;
> 		y/=10;
> 	}
> 	return dif==1;
>
> }
> int main()
> {
>         ios::sync_with_stdio(0);
> 	for(int i=1000;i<10000;i++)
> 	{
> 		prime[i]=1;
> 		for(int j=2;j*j<=i;j++)
> 		{
> 			if(i%j==0)
> 			{
> 				prime[i]=0;
> 				break;
> 			}
> 		}
> 		if(prime[i]) primes.push_back(i);
> 	}
> 	int x,y;
> 	for(auto x: primes)
> 	{
> 		for(auto y : primes)
> 		{
> 			if(isValid(x,y))
> 				a[x].push_back(y);
> 		}
> 	}
> 	int times;
> 	cin>>times;
> 	while(times--)
> 	{
> 		int from,to;
> 		cin>>from>>to;
> 		memset(d,-1,sizeof d);
> 		queue<int> q;
> 		d[from]=0;
> 		q.push(from);
> 		while(!q.empty() && d[to]<0)
> 		{
> 			int x=q.front();
> 			q.pop();
> 			for(auto y :a[x])
> 			{
> 				if(d[y]<0)
> 				{
> 					d[y]=d[x]+1;
> 					q.push(y);
> 				}
> 			}
> 		}
> 		cout<<d[to]<<endl;
> 	}
> 	return 0;
> }
> 苦思半天，找错后：
> #include<iostream>
> #include<cstdio>
> #include<vector>
> #include<cmath>
> #include<algorithm>
> #include<string>
> #include<set>
> #include<map>
> #include<ctime>
> #include<cstring>
> #include<cassert>
> #include<bitset>
> #include<sstream>
> #include<queue>
> using namespace std;
> int prime[10100],d[10100];
> vector<int>a[10100],primes;
> int isValid(int x,int y)
> {
> 	int dif=0;
> 	for(int i=0;i<4;i++)
> 	{
> 		dif+=(x%10!=y%10);
> 		x/=10;
> 		y/=10;
> 	}
> 	return dif==1;
>
> }
> int main()
> {
> 	for(int i=1000;i<10000;i++)
> 	{
> 		prime[i]=1;
> 		for(int j=2;j*j<=i;j++)
> 		{
> 			if(i%j==0)
> 			{
> 				prime[i]=0;
> 				break;
> 			}
> 		}
> 		if(prime[i]) primes.push_back(i);
> 	}
> 	for(int i=0;i<primes.size();i++)
> 	{
> 		for(int j=0;j<primes.size();j++)
> 		{
> 			int x=primes[i];
> 			int y=primes[j];
> 			if(isValid(x,y))
> 				a[x].push_back(y);
> 		}
> 	}
> 	int times;
> 	cin>>times;
> 	while(times--)
> 	{
> 		int from,to;
> 		cin>>from>>to;
> 		memset(d,-1,sizeof d);
> 		queue<int> q;
> 		d[from]=0;
> 		q.push(from);
> 		while(!q.empty() && d[to]<0)
> 		{
> 			int x=q.front();
> 			q.pop();
> 			for(int i=0;i<a[x].size();i++)
> 			{
> 				int y=a[x][i];
> 				if(d[y]<0)
> 				{
> 					d[y]=d[x]+1;
> 					q.push(y);
> 				}
> 			}
> 		}
> 		cout<<d[to]<<endl;
> 	}
> 	return 0;
> }

Followed by: