穿越虫洞

问题描述

小H有 $n$ 个秘密基地（编号 $1$ 到 $n$ ）, $n$ 个秘密基地之间有 $m$ 条双向路径和 $w$ 个单向时空隧道，通过路径需要消耗一定的时间 $T_i$ ，而通过时空隧道可以使时光倒流 $T_j$ ,现在小H想知道他能否从某一秘密基地出发，通过路径和时空隧道回到过去（即回到出发的秘密基地且该时刻要早于出发时间）。

输入格式

第 $1$ 行，一个整数 $F$ ,表示测试用例的数量
接下来对于每一个测试用例，输入格式如下
第 $1$ 行，三个空格分隔的整数 $n,m,w$
第 $2$ 到 $m+1$ 行，三个空格分隔的数字 $s,e,t$ ，表示 $s,e$ 之间存在双向道路，通行需要消耗 $t$ ，允许两点间存在多条路径
第 $m+2$ 到 $m+w+1$ 行三个空间分隔的数字 $s,e,t$ ,表示存在从 $s$ 到 $e$ 的单向时空隧道，穿过时空隧道时光倒流 $t$

输出格式

对于每个测试用例，如果小H能回到过去则输出YES，否则输出NO
每个测试用例的输出占一行

样例输入

样例输出

NO
YES

数据规模和约定

$1\leq n\leq 500,1\leq m\leq 4\times 10^4,1\leq w\leq 200$
$1\leq T_i,T_j\leq 10^4$

#include <bits/stdc++.h>
using namespace std;
int f, n, m, w, s, e, t;
int dis[505], vis[505], cnt[505], head[505];
int tot = 0;  // 当前边的总数
struct edge {
    int u, v, w, next;
} edges[200000];

void addEdge(int u, int v, int w) {  // 加一条边
    edges[tot].u = u, edges[tot].v = v;
    edges[tot].next = head[u], edges[tot].w = w;
    head[u] = tot++;
}

bool spfa(int s) {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    memset(cnt, 0, sizeof(cnt));
    queue<int> q;
    dis[s] = 0;
    q.emplace(s);
    vis[s] = 1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for (int i = head[u]; i != -1; i = edges[i].next) {
            int &v = edges[i].v, &w = edges[i].w, newdis = dis[u] + w;
            if (dis[v] > newdis) {
                dis[v] = newdis;
                cnt[v] = cnt[u] + 1;
                if (cnt[v] >= n)
                    return true;  // 有负环，可以回到过去
                if (!vis[v]) {
                    vis[v] = 1;
                    q.emplace(v);
                }
            }
        }
    }
    return false;  // 不能回到过去
}

int main() {
    scanf("%d", &f);
    for (int i = 0; i < f; i++) {
        memset(head, -1, sizeof(head));  // 储存每个节点的第一条边的编号，-1表示没有边
        scanf("%d%d%d", &n, &m, &w);
        for (int i = 1; i <= n; ++i)  // 加入超级源点，以免题目给的图不联通
            addEdge(0, i, 0);
        ++n;// 加入超级源点后节点数目就变成n+1了，不能继续用旧的n进行cnt[v] >= n，否则会判断出错
        for (int j = 0; j < m; j++) {  // 读取双向的正边
            scanf("%d%d%d", &s, &e, &t);
            addEdge(s, e, t);  // 加一条边
            addEdge(e, s, t);
        }
        for (int j = 0; j < w; j++) {  // 读取单向的负边
            scanf("%d%d%d", &s, &e, &t);
            addEdge(s, e, -t);  // 插入负边
        }
        if (spfa(0))  // 如果能回到过去
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}