1 //思路：把最长路转变为最短路，也就是将边权取负，最后再把负取正 2 #include<bits/stdc++.h> 3 using namespace std; 4 const int maxm = 50000; 5 const int maxn = 2000; 6 struct enkidu { 7 int y, nex, v; 8 }e[maxm]; 9 int inf; 10 int lin[maxn], len = 0; 11 int n, m; 12 int dis[maxn]; 13 bool vis[maxn], flag = 0; 14 15 inline int read() { 16 int x = 0, y = 1; 17 char ch = getchar(); 18 while(!isdigit(ch)) { 19 if(ch == '-') y = -1; 20 ch = getchar(); 21 } 22 while(isdigit(ch)) { 23 x = (x << 1) + (x << 3) + ch - '0'; 24 ch = getchar(); 25 } 26 return x * y; 27 } 28 29 inline void insert(int xx, int yy, int vv) { 30 e[++len].v = vv; 31 e[len].y = yy; 32 e[len].nex = lin[xx]; 33 lin[xx] = len; 34 } 35 36 queue<int> q; 37 inline void spfa(int st) { 38 q.push(st); 39 vis[st] = 1, dis[1] = 0; 40 while(!q.empty()) { 41 int k = q.front(); q.pop(); 42 vis[k] = 0; 43 for(int i = lin[k]; i; i = e[i].nex) { 44 int to = e[i].y, val = e[i].v; 45 if(dis[k] + val < dis[to]) { 46 dis[to] = dis[k] + val; 47 if(!vis[to]) { 48 vis[to] = 1; 49 q.push(to); 50 } 51 } 52 if(to == n) flag = 1; 53 } 54 } 55 } 56 57 int main() { 58 memset(vis, 0, sizeof(vis)); 59 memset(dis, 0x3f3f, sizeof(dis)); 60 n = read(), m = read(); 61 for(int i = 1; i <= m; ++i) { 62 int x, y, v; 63 x = read(), y = read(), v = read(); 64 insert(x, y, -v); 65 } 66 spfa(1); 67 if(!flag) cout << -1 << ' '; 68 else cout << dis[n] * -1 << ' '; 69 return 0; 70 }