题目大意

求是否有负环

思路

用Bellman-ford算法暴力判断一下就可以了

#include <stdio.h>
#define maxn 10000
#define INF 0x7f7f7f7f
int n,m,c;
struct arr
{
    int x,y,w;
}edge[maxn];
int d[maxn];
int ford(int x)
{
    int fl=0;
    for (int i=1;i<=n;i++)
        d[i]=INF;
    d[1]=0;
    for (int i=1;i<=n-1;i++)
    {
        fl=1;
        for (int j=1;j<=x;j++)
        {
            if (d[edge[j].x]>d[edge[j].y]+edge[j].w)
            {
                d[edge[j].x]=d[edge[j].y]+edge[j].w;
                fl=0;
            }
        }
        if (fl) break;
    }
    for (int i=1;i<=x;i++)
        if (d[edge[i].x]>d[edge[i].y]+edge[i].w)
            return 0;
    return 1;
}
int main()
{
    int t;
    scanf("%d",&t);
    for (int k=1;k<=t;k++)
    {
        scanf("%d%d%d",&n,&m,&c);
        for (int i=1;i<=m+c;i++)
            edge[i]=(arr){0,0,0};
        int l=0;
        for (int i=1;i<=m;i++)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            edge[++l]=(arr){x,y,z};
            edge[++l]=(arr){y,x,z};
        }
        for (int i=1;i<=c;i++)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            edge[++l]=(arr){x,y,-z};
        }
        if (ford(l))
            printf("NO\n");
        else printf("YES\n");
    }
}