记录编号	43394	评测结果	AAATTEAAA
题目名称	[NOIP 2010冲刺七]最长路	最终得分	66
用户昵称	Cloud	是否通过	未通过
代码语言	C++	运行时间	2.474 s
提交时间	2012-10-10 10:31:05	内存使用	37.67 MiB

#include<fstream>
#include<queue>
using namespace std;
struct
{
	long long a[1501];
	long long b[1501];
	long long  num;
}map[1501];
struct yu
{
	long long l;
	long long v;
};
queue<yu> dq;
yu tmp;
int main(void)
{
	ifstream fin("longest.in");
	ofstream fout("longest.out");
	long long n,m;
	long long i,j,k;
	long long max=-1;
	fin>>n>>m;
	for(k=0;k<m;k++)
	{
		fin>>i>>j;
		map[i].a[map[i].num]=j;
		fin>>map[i].b[map[i].num];
		map[i].num++;
	}
	for(k=0;k<map[1].num;k++)
	{
		tmp.l=map[1].a[k];
		tmp.v=map[1].b[k];
		if(tmp.l==n)
			if(tmp.v>max)
				max=tmp.v;
		dq.push(tmp);
	}
	while(dq.size())
	{
		tmp=dq.front();
		i=tmp.l;
		for(k=0;k<map[i].num;k++)
		{
			tmp.v+=map[i].b[k];
			tmp.l=map[i].a[k];
			if(tmp.l==n)
				if(tmp.v>max)
					max=tmp.v;
			dq.push(tmp);
			tmp=dq.front();
		}
		dq.pop();
	}
	fout<<max;
	fin.close();
	fout.close();
	return 0;
}