记录编号	420258	评测结果	AAAAAAAAA
题目名称	[NOIP 2010冲刺七]最长路	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.039 s
提交时间	2017-07-04 10:47:08	内存使用	0.58 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

inline char getc(void){
	static char buf[1 << 18], *fs, *ft;
	return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
} 

inline int in(void){
	register char tmp = getc();
	register int res = 0;
	while(!isdigit(tmp)) tmp = getc();
	while(isdigit(tmp))
		res = (res + (res << 2) << 1) + (tmp ^ 48),
		tmp = getc();
	return res;
}

const int MAXN = 1510;

struct EDGE{
	int to, val;
	EDGE *ne;
	
	EDGE(){;}
	EDGE(int a, EDGE *b, int c){
		to = a;
		val = c;
		ne = b;
	}
};

EDGE *head[MAXN];
int dis[MAXN];
int N, M, u, v, tmp;
bool inq[MAXN];
queue<int> que;

int main(){
#ifndef LOCAL
	freopen("longest.in", "r", stdin);
	freopen("longest.out", "w", stdout);
#else
	freopen("test.in", "r", stdin);
#endif
	memset(dis, 0xff, sizeof(dis));
	N = in(), M = in();
	
	for(int i = 1, fr, to; i <= M; ++i){
		fr = in(), to = in();
		head[fr] = new EDGE(to, head[fr], in());
	}
	
	dis[1] = 0;
	inq[1] = true;
	que.push(1);
	
	do{
		u = que.front();
		inq[u] = false;
		que.pop();
		
		for(register EDGE *e = head[u]; e; e = e->ne){
			if(dis[v = e->to] >= (tmp = (dis[u] + e->val))) continue;
			dis[v] = tmp;
			if(inq[v]) continue;
			que.push(v);
			inq[v] = true;
		}
	}while(!que.empty());
	
	printf("%d", dis[N]);
	return 0;
}