题解 P2850 【[USACO06DEC]虫洞Wormholes】

动态WA · 2019-08-08 14:10:37 · 题解

众所周知，这是一道判断有没有负环的模板题

SPFA判负环太难打？

Floyd时间太长？

选择打表Bellman-Ford，简单的理解，简单的代码

SPFA只是在它的基础上修改

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int F,h;
int n,m,w;
struct edge{
    int x,y,v;
}e[5500];
int d[501];
bool bellman(){
    memset(d,0x3f,sizeof(d));
    d[1]=0;
    for (int i=1;i<n;i++)
        for (int j=1;j<=h;j++)
            if (d[e[j].x]+e[j].v<d[e[j].y])
                d[e[j].y]=d[e[j].x]+e[j].v;
   //经过n-1次更新，此时答案应为最短路
    for (int j=1;j<=h;j++)
        if (d[e[j].x]+e[j].v<d[e[j].y]) return 1;
   //若还能更新，说明存在负环
    return 0;
}
int main(){
    scanf("%d",&F);
    for (int i=1;i<=F;i++){
        h=0;
        scanf("%d%d%d",&n,&m,&w);
        for (int i=1;i<=m;i++){
            int u,v,c;
            scanf("%d%d%d",&u,&v,&c);
            e[++h].x=u;
            e[h].y=v;
            e[h].v=c;
            e[++h].x=v;
            e[h].y=u;
            e[h].v=c;
        }
        for (int i=1;i<=w;i++){
            int u,v,c;
            scanf("%d%d%d",&u,&v,&c);
            e[++h].x=u;
            e[h].y=v;
            e[h].v=-c;
        }
        if (bellman()) printf("YES\n");
        else printf("NO\n");
    }
}