题意是有n个农场，农场有N块地，其中M条路是双向的，S条路是单向的。双向的路权值为正，单向的路权值为负。需要判断有没有负环。
以下是bellman_ford算法，需要注意的地方在注释里边。
1 #include<stdio.h>
2 #include<string.h>
3 #define INF 0x1f1f1f1f
4 #define MAX 5500
5 int dist[MAX/10];
6 struct edge
7 {
8 int u,v,w; //u为起点 v为终点 w是权值
9 }edge[MAX];
10 int bellman_ford2(int n,int m,int s) //n个点，m条边，起点是s
11 {
12 memset(dist,0x1f1f,sizeof(dist));
13 dist[s]=0;
14 int i,j,k,p,u,v;
15 bool flag;
16 for(i=1;i<n;i++) //n-1次迭代
17 {
18 flag=false; //用来标记某一次是否是更新
19 for(j=0;j<m;j++) //对每条边进行松弛，即迭代一次
20 {
21 u=edge[j].u;
22 v=edge[j].v;
23 if(dist[v]>dist[u]+edge[j].w)
24 {
25 dist[v]=dist[u]+edge[j].w;
26 flag=true; //如果这一次有某条边可以松弛
27 }
28 }
29 if(!flag) //如果某一次所有边都没有松弛，
30 return 1; // 可以确定没有负环，返回 1
31 }
32 flag=false;
33 for(i=0;i<m;i++) //对所有边进行第n次松弛
34 {
35 u=edge[i].u;
36 v=edge[i].v;
37 if(dist[v]>dist[u]+edge[i].w)
38 {
39 dist[v]=dist[u]+edge[i].w;
40 flag=true;
41 }
42 if(flag) return -1; //如果还有更新，有负环 返回 -1
43 }
44 return 1; //否则返回 1
45 }
46 int main()
47 {
48 int i,j,k,m,n,p,q,N,M;
49 int S;
50 scanf("%d",&n);
51 for(i=1;i<=n;i++)
52 {
53 scanf("%d%d%d",&N,&M,&S);
54 int t=0;
55 for(j=1;j<=M;j++)
56 {
57 scanf("%d%d%d",&p,&q,&k);
58 edge[t].u=p; //由于边是双向的，需要是两条
59 edge[t].v=q;
60 edge[t].w=k; t++;
61 edge[t].u=q;
62 edge[t].v=p;
63 edge[t].w=k; t++;
64 }
65 for(j=1;j<=S;j++)
66 {
67 scanf("%d%d%d",&p,&q,&k);
68 edge[t].u=p;
69 edge[t].v=q;
70 edge[t].w=-1*k; t++; //单向的边权值为负
71 }
72 if(bellman_ford2(N,S+2*M,1)==-1) //如果有负环 YES
73 printf("YES\n");
74 else
75 printf("NO\n");
76 }
77 }
78