思路与算法

每条普通路加入两个方向正向耗时，每个虫洞加入一个方向的负耗时。令所有顶点初始距离为0，相当于添加超级源。连续做最多N轮全边松弛；某一轮没有变化则无负环，若第N轮仍能变化则有负环。

正确性说明

普通路和虫洞的边权符号恰好对应时间变化。所有顶点从超级源可达，故不会漏掉非1号分量中的负环。没有负环时最短简单路最多N-1条原边，足够轮数后不会继续降低；存在负环时可沿环反复降低，仍能松弛。Bellman-Ford负环判定因此与是否能回到出发前的时刻等价。

复杂度

设E=2M+W，每组O(NE)，距离初始化O(N)、读边O(E)，已包含；空间O(N+E)。最多5组、N500、M2500、W200。64位距离覆盖松弛中间值，普通路重复或自环也原样处理。

易错点

必须检测全图而非只给dist[1]=0。虫洞输入T按有向边权-T处理，严格负的环才算，零环不算。完整范围提示写|T|≤10^4，参考程序保留符号处理，不擅自把负T截为0。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct Edge {
    int u, v, w;
};
int main() {
    int F;
    cin >> F;
    while (F--) {
        int n, m, W;
        cin >> n >> m >> W;
        vector<Edge> e;
        for (int i = 0, u, v, w; i < m; ++i) {
            cin >> u >> v >> w;
            e.push_back({u - 1, v - 1, w});
            e.push_back({v - 1, u - 1, w});
        }
        for (int i = 0, u, v, w; i < W; ++i) {
            cin >> u >> v >> w;
            e.push_back({u - 1, v - 1, -w});
        }
        vector<long long> d(n);
        bool changed = false;
        for (int it = 0; it < n; ++it) {
            changed = false;
            for (auto edge : e)
                if (d[edge.v] > d[edge.u] + edge.w) {
                    d[edge.v] = d[edge.u] + edge.w;
                    changed = true;
                }
            if (!changed)
                break;
        }
        cout << (changed ? "YES" : "NO") << '\n';
    }
}