编辑代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
#include<climits>
using namespace std;
const int maxn = 1e6 + 5;
const int xx = 1e3;
int check[maxn] = { 0 };
inline int read() {
	register int x = 0; bool flag = 1; char ch = getchar();
	while (ch < '0' or ch>'9') { if (ch == '-')flag = 0; ch = getchar(); }
	while (ch >= '0' and ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
	if (flag)return x;
	return ~(x - 1);
}
inline void write(int x) {
	if (x < 0) { x = ~(x - 1); putchar('-'); }
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
struct edge {
	int from, to, dis;
}k;
long long in[maxn];//记录每个点的入度
vector<edge> e[maxn];//邻接表存图 
queue<int> q;
int n, m;
long long dp[maxn] = {-INT_MAX};
int main() {
	n = read(); m = read();
	if (m == 0) {
		cout << -1;
		return 0;
	}
	for (register int i = 1; i <= m; i++) {//建立有向无环图
		k.from = read(); k.to = read(); k.dis = read();
		e[k.from].push_back(k);
		in[k.to]++;//入度加一	
	}
	for (register int i = 1; i <= n; i++) {
		if (in[i] == 0)
			q.push(i);
	}
	dp[n] = -1;//初始化
	check[1] = 1;
	while (!q.empty()) {//拓扑排序
		register int u = q.front();
		q.pop();
		for (register int j= 0; j < e[u].size(); j++) {
			register int v = e[u][j].to;
			in[v]--;
			if (check[u]) {//从一号节点开始
				dp[v] = max(dp[v], dp[u] + e[u][j].dis);
				check[v] = 1; 
			}
			if (in[v] == 0)
				q.push(v);
		}
	}
	write(dp[n]);
	return 0;
}