记录编号	43345	评测结果	AAAAAAAAA
题目名称	[NOIP 2010冲刺七]最长路	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.061 s
提交时间	2012-10-09 22:18:29	内存使用	3.33 MiB

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int MAXN=1600;
vector<int> map[MAXN],val[MAXN];
int N,M,dist[MAXN]={0},flag[MAXN]={0};

inline void init()
{
	scanf("%d %d\n",&N,&M);int a,b,c;
	for(int i=2;i<=N;i++) dist[i]=-1;
	for(int i=1;i<=M;i++)	
	{
		scanf("%d %d %d\n",&a,&b,&c);
		map[a].push_back(b);
		val[a].push_back(c);
	}
}

queue<int> q;
inline void bfs()
{
	q.push(1); flag[1]=1;
	int u,v,c;
	while(q.size())
	{
		u=q.front(); q.pop(); flag[u]=0;
		for(unsigned int i=0;i<map[u].size();i++)
		{
			v=map[u][i],c=dist[u]+val[u][i];
			if(c<=dist[v]) continue;
			dist[v]=c; if(flag[v]) continue;
			flag[v]=1; q.push(v);
		}
	} 
	printf("%d\n",dist[N]);
}

int main()
{
	freopen("longest.in","r",stdin);
	freopen("longest.out","w",stdout);
	init(); bfs();
	return 0;
}