前言：这个题目中有负权重的边，狄克斯特拉算法坑定是用不了的，学一下spfa算法吧，发现就是bellman算法的队列优化
还有一个关键就是我们求最长的权重，我们要将边权重变为-的，最后答案取反就行

---

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;#define int long long
const int N = (int)5e4+5;
int e[N],ne[N],h[N], idx = 0;
int w[N];
int n,m;
int dis[N],vis[N];void add(int a,int b,int wei){e[++idx] = b, ne[idx] = h[a], h[a] = idx;w[idx] = wei;
}void spa(){for(int i=0;i<=n;i++){dis[i] = 0x3fffffff;}dis[1] = 0; vis[1] = 1;queue<int> q; // 用来装松弛的点 q.push(1);while(q.size()){int u = q.front(); q.pop();vis[u] = 0; // 出栈for(int i=h[u];i;i=ne[i]){int to = e[i], ww = w[i];if(dis[u]+ww<dis[to]){dis[to] = dis[u] + ww;if(!vis[to]) q.push(to);}} }
}signed main(){cin >> n >> m;for(int i=1;i<=m;i++){int u,v,x; cin >> u >> v >> x;add(u,v,-x);}spa();if(dis[n]==0x3fffffff){cout << -1;}else cout << -dis[n];return 0;
}

---

那么我们队列优化的还可以查询负环吗，答案是可以的，我们可以增加一个cnt数组，记录最短路的长度，长度超过n就是存在

---

struct edge {int v, w;
};vector<edge> e[maxn];
int dis[maxn], cnt[maxn], vis[maxn];
queue<int> q;bool spfa(int n, int s) {memset(dis, 0x3f, (n + 1) * sizeof(int));dis[s] = 0, vis[s] = 1;q.push(s);while (!q.empty()) {int u = q.front();q.pop(), vis[u] = 0;for (auto ed : e[u]) {int v = ed.v, w = ed.w;if (dis[v] > dis[u] + w) {dis[v] = dis[u] + w;cnt[v] = cnt[u] + 1;  // 记录最短路经过的边数if (cnt[v] >= n) return false;// 在不经过负环的情况下，最短路至多经过 n - 1 条边// 因此如果经过了多于 n 条边，一定说明经过了负环if (!vis[v]) q.push(v), vis[v] = 1;}}}return true;
}