记录编号	43664	评测结果	AAAAAAAAA
题目名称	[NOIP 2010冲刺七]最长路	最终得分	100
用户昵称	万里长城	是否通过	通过
代码语言	C++	运行时间	0.032 s
提交时间	2012-10-12 13:10:38	内存使用	0.90 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <deque>
#include <cmath>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define clr(x, n) memset(x, n, sizeof(x))
#define inf 0x7fffffff
#define maxn 1505
using namespace std;

void setIO(string name) {
	string in_f = name + ".in";
	string out_f = name + ".out";
	freopen(in_f.c_str(), "r", stdin);
	freopen(out_f.c_str(), "w", stdout);
}

struct alist {
	int v, w, next;
};

alist map[50005];
int head[maxn];
int n, m;
int dis[maxn];
bool visit[maxn];
deque<int> que;

void init() {
	clr(dis, 0);
	clr(visit, false);
	clr(head, -1);
	scanf("%d%d", &n, &m);
	int x, y, z;
	rep(i, m) {
		scanf("%d%d%d", &x, &y, &z);
		x--;
		y--;
		map[i].v = y;
		map[i].w = -z;
		map[i].next = head[x];
		head[x] = i;
	}
}

void insert(int x) {
	if (!visit[x]) {
		visit[x] = true;
		if (que.empty()) {
			que.push_back(x);
			return;
		}
		int t = que.front();
		if (dis[t] <= dis[x]) que.push_back(x);
		else que.push_front(x);
	}
}

void spfa() {
        insert(0);
        while(!que.empty()) {
                int t = que.front();
                int p = head[t];
		visit[t] = false;
                que.pop_front();
                while(p != -1) {
                        if (dis[t] + map[p].w < dis[map[p].v]) {
                                dis[map[p].v] = dis[t] +  map[p].w;
                                insert(map[p].v);
                        }
                        p = map[p].next;
                }
        }
}

void output() {
        if (!dis[n - 1]) printf("%d\n", -1);
        else printf("%d\n", -dis[n - 1]);
}

void solve() {
        spfa();
        output();
}

int main() {
        setIO("longest");
        init();
        solve();
        return 0;
}