我没有心态辣！！！

这道题卡了我很久。。。。。

首先说说我哪里被坑了吧

1.普通道路双向，虫洞单向（没有读清楚题的悲伤）
2.没有看y总视频就开始自己yy

一看到题，我就想的一个好方法

1.预处理边，把虫洞当成负边处理存入数组（不建图）
2.枚举起点
3.建反图
4.dfs确定起点在反图上可以到达那些点（相当于在正图上，这些点可以到达起点）
5.建正图，如果边的终点不能到达 第2步枚举的起点（参考第4步）就不加入边（避免不必要的边）
6.spfa一波，如果有负换，输出YES，如果没有负环，那么换个起点继续搜

不出我所料，他超时了 ╮(╯﹏╰）╭

我洋洋洒洒102代码啊啊啊啊！！！

超时代码

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
struct oppo {
    int to,s,nest;
} rood[6005];
int head[600],tot;
int n,m,w,a,b,c;
void add(int from,int to,int s) {
    rood[++tot].s=s;
    rood[tot].to=to;
    rood[tot].nest=head[from];
    head[from]=tot;
}
int vis[600];
int f[600];
int all[600];
stack< int > v;
bool spfa(int x) {
    memset(all,0,sizeof(all));
    memset(vis,10,sizeof(vis));
    memset(f,0,sizeof(f));
    vis[x]=0;
    v.push(x);
    while(v.size()) {
        int lxl=v.top();
        f[lxl]=0;
        v.pop();
        for(int i=head[lxl]; i; i=rood[i].nest) {
            if(vis[lxl]+rood[i].s<vis[rood[i].to]) {
                vis[rood[i].to]=vis[lxl]+rood[i].s;
                all[rood[i].to]=all[lxl]+1;
                if(all[rood[i].to]>n||vis[x]<0) {
                    puts("YES");
                    return 0;
                }
                if(!f[rood[i].to]) {
                    f[rood[i].to]=1;
                    v.push(rood[i].to);
                }
            }
        }
    }
    return 1;
}
int from[6005],to[6005],s[6005];
bool h[600];
void dfs(int x) {
    h[x]=1;
    for(int i=head[x]; i; i=rood[i].nest)
        if(!h[rood[i].to])
            dfs(rood[i].to);
}
int main() {
    int T;
    cin>>T;
    while(T--) {
        memset(h,0,sizeof(h));
        tot=0;
        memset(head,0,sizeof(head));
        cin>>n>>m>>w;
        for(int i=1; i<=m; i++) {
            scanf("%d %d %d",&a,&b,&c);
            from[i]=a;
            to[i]=b;
            s[i]=c;
        }
        for(int i=1; i<=w; i++) {
            scanf("%d %d %d",&a,&b,&c);
            from[m+i]=a;
            to[m+i]=b;
            s[m+i]=-c;
        }
        bool flag=1;
        for(int i=1; i<=n&&flag; i++)
        {
            tot=0;
            memset(head,0,sizeof(head));
            for(int j=1;j<=m+w;j++)
            {
                add(to[j],from[j],s[j]);
                if(i<=m)
                    add(from[j],to[j],s[j]);
            }
            memset(h,0,sizeof(h));
            dfs(i);
            tot=0;
            memset(head,0,sizeof(head));
            for(int j=1; j<=m+w; j++)
                if(h[to[j]]) {
                    add(from[j],to[j],s[j]);
                    if(j<=m)
                        add(to[j],from[j],s[j]);
                }
            flag=spfa(i);
        }
        if(flag)
            puts("NO");
    }
    return 0;
}

改代码的途中，我陷入了对信息学的沉思

为什么！！！！

然后我发现，我为什么要枚举起点呢？？？
直接建图，如果有原图有负环，那么起点就在负环上呀！

我靠（小声BB）

就变成简单的判负环辣！！！

代码如下

#include<bits/stdc++.h>
using namespace std;
struct oppo {
    int to,s,nest;
} rood[6005];
int head[600],tot;
int n,m,w,a,b,c;
void add(int from,int to,int s) {
    rood[++tot].s=s;
    rood[tot].to=to;
    rood[tot].nest=head[from];
    head[from]=tot;
}
int vis[600];
int f[600];
int all[600];
stack< int > v;
bool flag[600];
bool spfa(int x) {
    memset(all,0,sizeof(all));
    memset(vis,10,sizeof(vis));
    memset(f,0,sizeof(f));
    vis[x]=0;
    v.push(x);
    while(v.size()) {
        int lxl=v.top();
        flag[lxl]=1;
        f[lxl]=0;
        v.pop();
        for(int i=head[lxl]; i; i=rood[i].nest) {
            if(vis[lxl]+rood[i].s<vis[rood[i].to]) {
                vis[rood[i].to]=vis[lxl]+rood[i].s;
                all[rood[i].to]=all[lxl]+1;
                if(all[rood[i].to]>n) {
                    puts("YES");
                    return 0;
                }
                if(!f[rood[i].to]) {
                    f[rood[i].to]=1;
                    v.push(rood[i].to);
                }
            }
        }
    }
    return 1;
}
int main() {
    int T;
    cin>>T;
    while(T--) {
        memset(flag,0,sizeof(flag));
        tot=0;
        memset(head,0,sizeof(head));
        cin>>n>>m>>w;
        for(int i=1; i<=m; i++) {
            scanf("%d %d %d",&a,&b,&c);
            add(a,b,c);
            add(b,a,c);
        }
        for(int i=1; i<=w; i++) {
            scanf("%d %d %d",&a,&b,&c);
            add(a,b,-c);
        }
        bool fff=1;
        for(int i=1;i<=n&&fff;i++)
            if(!flag[i])
                fff=fff&&spfa(i);
        if(fff)
            puts("NO");
    }
    return 0;
}