记录编号	221724	评测结果	AAAAAAAAA
题目名称	[NOIP 2010冲刺七]最长路	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.041 s
提交时间	2016-01-25 15:21:36	内存使用	0.79 MiB

#include<cstdio>
#include<queue>
using namespace std;
const int maxn = 1505,maxm = 50005;
struct edge{
	int w,to,next;
}lst[maxm];
int first[maxn],dis[maxn];
int len = 1;
void insert(int v1,int v2,int cost){
	lst[len].to = v2;
	lst[len].w = cost;
	lst[len].next = first[v1];
	first[v1] = len++;
}
bool inq[maxn];
void spfa(){
	queue<int> q;
	q.push(1);
	while(!q.empty()){
		int v = q.front();
		q.pop();
		inq[v] = false;
		for(int pt = first[v];pt;pt = lst[pt].next){
			if(dis[v]+lst[pt].w>dis[lst[pt].to]){
				dis[lst[pt].to] = dis[v]+lst[pt].w;
				if(!inq[lst[pt].to]){
					q.push(lst[pt].to);
					inq[lst[pt].to] = true;
				}
			}
		}
	}
}
int main(){
	freopen("longest.in","r",stdin);
	freopen("longest.out","w",stdout);
	int n,m;
	scanf("%d %d",&n,&m);
	int a,b,c;
	for(int i = 0;i<m;++i){
		scanf("%d %d %d",&a,&b,&c);
		insert(a,b,c);
	}
	if(m)spfa();
	if(dis[n]==0)printf("-1\n");
	else printf("%d\n",dis[n]);
	
	fclose(stdin);fclose(stdout);
	return 0;
}