题目描述

农夫约翰在巡视他的众多农场时，发现了很多令人惊叹的虫洞。

虫洞非常奇特，它可以看作是一条 单向 路径，通过它可以使你回到过去的某个时刻（相对于你进入虫洞之前）。

农夫约翰的每个农场中包含N片田地，M条路径（双向）以及W个虫洞。

现在农夫约翰希望能够从农场中的某片田地出发，经过一些路径和虫洞回到过去，并在他的出发时刻之前赶到他的出发地。

他希望能够看到出发之前的自己。

请你判断一下约翰能否做到这一点。

下面我们将给你提供约翰拥有的农场数量F，以及每个农场的完整信息。

已知走过任何一条路径所花费的时间都不超过10000秒，任何虫洞将他带回的时间都不会超过10000秒。
输入格式
第一行包含整数F，表示约翰共有F个农场。

对于每个农场，第一行包含三个整数N，M，W。

接下来M行，每行包含三个整数S，E，T，表示田地S和E之间存在一条路径，经过这条路径所花的时间为T。

再接下来W行，每行包含三个整数S，E，T，表示存在一条从田地S走到田地E的虫洞，走过这条虫洞，可以回到T秒之间。

输出格式
输出共F行，每行输出一个结果。

如果约翰能够在出发时刻之前回到出发地，则输出“YES”，否则输出“NO”。

数据范围
1≤F≤5
1≤N≤500,
1≤M≤2500,
1≤W≤200,
1≤T≤10000,
1≤S,E≤N

输入样例：

2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8

输出样例：

NO
YES

算法1

(spfa)

时间复杂度 一般表现$O(m)$，最坏$O(nm)$

C++ 代码

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 610, M = N * 10, inf = 0x3f3f3f3f;
struct Edge {
    int u;      // 边的起点
    int v;      // 边的终点
    int w;      // 边的权值 
} e[M];         // 边数组
int idx = 1;    // 顶点的游标
int h[N];       // 保存每条边的起点
int d[N];       // 保存每个顶点到起点的最短距
int inQue[N];   // 标记每个顶点是否已经在队列中
int cnt[N];     // 记录走过的顶点总数
int vst[N];     // 标记每个顶点是否已经访问过
int f, n, m1, m2;

void add(int u, int v, int w) {
    e[idx].w = w;   // 记录一条边的权值
    e[idx].v = v;     // 记录一条边的终点
    e[idx].u = h[u];  // 记录一条边的起点
    h[u] = idx++;       // 保存顶点编号
}

int spfa(int s) {
    memset(d, 0x3f, sizeof d);  // 初始化
    memset(cnt, 0, sizeof cnt);
    d[s] = inQue[s] = 0;
    queue<int> q;
    q.push(s);
    while(!q.empty()) {
        auto t = q.front();
        q.pop();
        int p = d[t], u = t;
        vst[u] = 1;
        inQue[u] = 0;
        for(int i = h[u]; i; i = e[i].u) {
            int v = e[i].v, w = e[i].w;
            if(d[v] <= p + w) continue; // 松弛失败，跳回
            d[v] = p + w;
            cnt[v] = cnt[u] + 1;
            if(cnt[v] >= n)  // 经过的顶点个数不小于n, 必然存在带负权边的环
                return 0;
            if(inQue[v]) continue; // 该顶点的编号已经在队列中，跳回
            inQue[v] = 1; // 否则，标记该顶点已经在队列中
            q.push(v);
        }
    }
    return 1;
} 

void init() { // 初始化
    idx = 1;
    memset(h, 0, sizeof h);
    memset(vst, 0, sizeof vst);
    memset(inQue, 0, sizeof inQue);
}

int main() {
    cin >> f;
    while(f--) {
        init();
        cin >> n >> m1 >> m2;
        int u, v, w;
        for(int i = 1; i <= m1; i++) {
            cin >> u >> v >> w;
            add(u, v, w);
            add(v, u, w);
        }
        for(int i = 1; i <= m2; i++) {
            cin >> u >> v >> w;
            add(u, v, -w);
        }
        int claim = 1;  // 1表示断言所有田块不存在虫洞
        for(int i = 1; i <= n; i++) { // 一旦找到虫洞立即结束
            if(vst[i] || spfa(i)) continue;  // 访问过的顶点或到当前为止未找到虫洞，继续查找
            claim = 0; // 否则，找到虫洞
            break;
        }
        if(claim) puts("NO");
        else puts("YES");
    }
    return 0;
}

算法2

(贝尔曼-福特) $O(nm)$

时间复杂度

C++ 代码

#include <iostream>
#include <cstring>
using namespace std;
const int N = 510, M = 10010, INF = 0x3f3f3f3f; 
struct Edge {
    int u, v, w;
} e[M];
int idx;
int d[N], f, n, m1, m2, u, v, w;

void add(int u, int v, int w) {
    e[idx].w = w;
    e[idx].v = v;
    e[idx].u = u;
    idx++;
}

int bellman_ford(int k, int m) {
    int claim;
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    for(int i = 1; i <= k; i++) {
        claim = 1;  // 1表示断言每个田块都不存在虫洞，即每个顶点都没有负权边
        for(int j = 0; j < m; j++) {
            int u = e[j].u, v = e[j].v, w = e[j].w;
            if(d[v] <= d[u] + w) continue;
            d[v] = d[u] + w;
            claim = 0;
        }
        if(claim) break;
    }
    claim = 1;
    for(int i = 0; i < m; i++) {
        int u = e[i].u, v = e[i].v, w = e[i].w;
        if(d[v] <= d[u] + w) continue;
        claim = 0;
        break;
    }
    return claim;
}

int main() {
    cin >> f;
    while(f--) {
        idx = 0;
        cin >> n >> m1 >> m2;
        for(int i = 0; i < m1; i++) {
            cin >> u >> v >> w;
            add(u, v, w);
            add(v, u, w);
        }
        for(int i = 0; i < m2; i++) {
            cin >> u >> v >> w;
            add(u, v, -w);
        }
        int t = bellman_ford(n - 1, idx); 
        if(!t) puts("YES");
        else puts("NO");
    }
    return 0;
}