记录编号	48745	评测结果	AAAAAAAA
题目名称	过河	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	C++	运行时间	0.260 s
提交时间	2012-11-06 15:02:53	内存使用	9.04 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<utility>
#include<algorithm>
using namespace std;
int n,w[1005][3],f[11]={0},sum=1,ff[11]={-5,-4,-3,-2,-1,0,1,2,3,4,5};
bool maxn[1005][6000]={0};
queue<pair<int,int> >q;
int tmp,tt,ttt;
void bfs();
int main()
{
	freopen ("rivera.in","r",stdin);
	freopen ("rivera.out","w",stdout);
	cin>>n;
	for (int i=1;i<=n;i++)
	{
		cin>>w[i][0]>>w[i][1];
		w[i][2]=w[i][0]+w[i][1];
		f[w[i][2]]=1;
	}
	/*for (int i=10;i>=2;i--)
	{
		for (int j=i-1;j>=2;j--)
		{
			if (f[i]&&f[j]&&i!=j)
			{
				if (i%j==0)
					f[j]=0;
			}
		}
	}
	for (int i=2;i<=10;i++)
	{
		if (f[i])
			sum*=i;
	}*/
	bfs();
	cout<<"NO";
	return 0;
}

void bfs()
{
	pair<int,int>temp;
	temp.first=0;
	temp.second=0;
	q.push(temp);
	maxn[0][0]=1;
	while (!q.empty())
	{
		for (int i=0;i<11;i++)
		{
			tmp=q.front().first+ff[i];
			tt=q.front().second+1;
			if (tt>6000)
				return;
			if (tmp==n+1)
			{
				cout<<tt;
				exit(0);
			}
			if (tmp==0)
			{
				if (!maxn[tmp][tt])
				{
					temp.first=tmp;
					temp.second=tt;
					q.push(temp);
					maxn[tmp][tt]=1;
				}
			}
			if (tmp>0&&tmp<=n)
			{
				ttt=tt%(w[tmp][2]);
				if (ttt>=1&&ttt<=w[tmp][0]&&!maxn[tmp][tt])
				{
					temp.first=tmp;
					temp.second=tt;
					q.push(temp);
					maxn[tmp][tt]=1;
					
				}
			}
		}
		q.pop();
	}
}