记录编号	317098	评测结果	AAAAAAAAA
题目名称	[NOIP 2010冲刺七]最长路	最终得分	100
用户昵称	Hzoi_Go灬Fire	是否通过	通过
代码语言	C++	运行时间	0.038 s
提交时间	2016-10-07 17:29:59	内存使用	0.79 MiB

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<iostream>
#define Begin freopen("longest.in","r",stdin);freopen("longest.out","w",stdout);
#define End fclose(stdin);fclose(stdout);
using namespace std;
const int maxn=1510;
struct Edge{
	int next,to,dis;
}e[50000];
int n,m,head[maxn],len;
void Insert(int x,int y,int z){
	len++;e[len].to=y;e[len].next=head[x];e[len].dis=z;head[x]=len;
}
void Init();
void Spfa(int x){
	queue<int> q; 
	int dis[maxn];memset(dis,-0x7f,sizeof(dis));dis[x]=0;
	bool f[maxn];f[x]=1;
	q.push(x);
	while(!q.empty()){
		int k=q.front();q.pop();f[k]=0;
		for(int i=head[k];i;i=e[i].next){
			int j=e[i].to;
			if(dis[j]<dis[k]+e[i].dis){
				dis[j]=dis[k]+e[i].dis;
				if(!f[j]){q.push(j);f[j]=1;}
			}
		}
	}
	if(dis[n]<-515313515)printf("-1\n");
	else printf("%d\n",dis[n]);
} 
int main(){
    Begin;
    Init();
    //system("pause");
    End;
    return 0;
}
void Init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y,z;scanf("%d%d%d",&x,&y,&z);
		Insert(x,y,z);
	}
	Spfa(1);
}