题目链接： 传送门
#include<cstdio> #include<algorithm> #include<cstring> #include<queue> #define INF 0x3f3f3f3f using namespace std; const int N = 10010; //这里用邻接表来存图 int h[N], val[N], e[N], ne[N], idx, n, m, w; // d[x]存储1号点到x的最短距离，cnt[x]存储1到x的最短路中经过的点数 int d[N], cnt[N]; // 存储每个点是否在队列中 bool used[N]; //往邻接表添加元素 void add(int a, int b, int c) { e[idx] = b, val[idx] = c, ne[idx] = h[a], h[a] = idx++; } //如果邻接表存在该元素则更新，否则往邻接表添加元素 void update(int a, int b, int c) { for (int i = h[a]; i != -1; i = ne[i]) { if(e[i] == b) { val[i] = c; return; } } e[idx] = b, val[idx] = c, ne[idx] = h[a], h[a] = idx++; } //spfa来判断是否形成负环 bool spfa() { //初始化 memset(d, INF, sizeof(d)); memset(used, 0, sizeof(used)); memset(cnt, 0, sizeof(cnt)); queue<int> q; //判断从各个点开始的负环 for (int i = 1; i <= n; i++) { q.push(i); used[i] = 1; } while (q.size()) { int cur = q.front(); q.pop(); used[cur] = 0; for (int i = h[cur]; i != -1; i = ne[i]) { int j = e[i]; if (d[j] > d[cur] + val[i]) { d[j] = d[cur] + val[i]; cnt[j] = cnt[cur] + 1; //跳出条件 if (cnt[j] >= n) return 1; if (!used[j]) { q.push(j); used[j] = 1; } } } } return 0; } int main() { int t; scanf("%d", &t); while(t--) { //初始化各个头结点 memset(h, -1, sizeof(h)); //重新开始存数据 idx = 0; scanf("%d%d%d", &n, &m, &w); int a, b, c; //添加两个边（因为它是双向通道，等于添加两个同边权值的有向边） for(int i = 0; i < m; i++) { scanf("%d%d%d", &a, &b, &c); add(a, b, c); add(b, a, c); } //更新或添加负边权 for(int i = 0; i < w; i++) { scanf("%d%d%d", &a, &b, &c); update(a, b, -c); } if(spfa()) puts("YES"); else puts("NO"); } return 0; }这道题一开始题目没怎么看懂，后来才明白这道题其实就是判断是否存在负环。这道题我用了spfa来判断负环这里有一篇关于spfa的博客 讲讲整道题的思路，首先先接受双向的正权值的边，然后把这些边加入到邻接表中（有关邻接表的知识）然后接受负边权的边，如果边已存在则更新其权值，如果边不存在，则添加进去，然后直接套spfa的模板判断是否有负环。有则输出YES，反之则输出NO。
