题意：N个顶点， M条双向边， W条权值为负的单向边。求是否存在负环。
思路：首先你要懂bellman-ford或spfa。。这是基础的spfa判断是否存在负环的题，存在负环的节点会重复入队（因为最短路在不断变小）， 所以只要有节点重复入队超过n次，即可判断存在负环（即开一个数组记录节点入队次数）。
总结：本来是想求出每对节点之间的最短路，看是否存在负的，结果果断TLE。后来才想起spfa可以处理负环云云~~
AC代码：
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<vector>
#include<climits>
#include<cstring>
using namespace std;
#define maxn 600
#define INF 10000000
struct node
{
int to, dist;
};
vector<node> g[maxn];
int n, m, w;
int cnt[maxn], d[maxn];
void input()
{
scanf("%d%d%d", &n, &m, &w);
for(int i = ; i < n+; i++) g[i].clear();
for(int i = ; i < m; i++){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
g[a].push_back((node){b, c});
g[b].push_back((node){a, c});
}
for(int i = ; i < w; i++) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
c = -c;
g[a].push_back((node) {b, c});
}
}
bool spfa(int s)
{
for(int i = ; i <= n; i++) d[i] = INF, cnt[i] = ;
d[s] = ;
cnt[s] = ;
queue<int> q;
q.push(s);
bool inq[maxn]; memset(inq, , sizeof(inq));
inq[s] = true;
while(!q.empty()){
int t = q.front(); q.pop();
inq[t] = false;
int l = g[t].size();
for(int i = ; i < l; i++){
int to = g[t][i].to, dist = g[t][i].dist;
if(d[to] > d[t] + dist) {
d[to] = d[t] + dist;
if(!inq[to]){
inq[to] = ;
cnt[to]++;
if(cnt[to] >= n) return true;
q.push(to);
}
}
}
}
return false;
}
void work()
{
input();
if(spfa()) printf("YES\n");
else printf("NO\n");
} int main()
{
int t ; cin>>t;
while(t--){
work();
}
return ;
}