虫洞 (wormhole. cpp/c/pas)

题目描述

John 在他的农场中闲逛时发现了许多虫洞. 虫洞可以看作一条十分奇特的有向边, 并可以使 你返回到过去的一个时刻 (相对你进入虫洞之前). John 的每个农场有 M 条小路 (无向边) 连接着 N (从 1...... N 标号) 块地, 并有 W 个虫洞 (有向边). 其中:

\[1 \leq N \leq 500, 1 \leq M \leq 2500, 1 \leq W \leq 200\]

现在 John 想借助这些虫洞来回到过去 (出发时刻之前), 请你告诉他能办到吗. John 将向 你提供 \(F (1 \leq F \leq 5)\) 个农场的地图. 没有小路会耗费你超过 10000 秒的时间, 当然也没有虫洞回帮你回到超过 10000 秒以前.

输入格式

Line 1: 一个整数 F, 表示农场个数.

Line 1 of each farm: 三个整数 N, M, W.

Lines 2...... M+1 of each farm: 三个数 (S, E, T). 表示在标号为 S 的地与标号为 E 的地中间有一条用时 T 秒的小路.

Lines M+2...... M+W+1 of each farm: 三个数 (S, E, T). 表示在标号为 S 的地与标号为 E 的地中间有一条可以使 John 到达 T 秒前的虫洞.

输出格式

Lines 1...... F: 如果 John 能在这个农场实现他的目标, 输出 “YES” , 否则输出 “NO” .

样例输入

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

Explanation

一个判断负权回路的最短路算法裸题~

直接 SPFA 水过~

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cstring>

using namespace std;
typedef long long lli;
const int maxn = 1000, maxm = 100001;
const lli infinit = 0x7ffffff;

class SPFA
{
public:
    struct edge
    {
        int u, v;
        lli len;
        edge *next;
    } *edges[maxn], epool[maxm];
    int n, ecnt;
    lli dist[maxn];
    bool inque[maxn];
    void addedge(int u, int v, lli len)
    {
        edge *p = &epool[ecnt++];
        p->u = u; p->v = v; p->len = len;
        p->next = edges[u]; edges[u] = p;
        return ;
    }
    bool flag;
    void spfa(int p)
    {
        inque[p] = true;
        for (edge *ep = edges[p]; ep; ep = ep->next)
            if (dist[p] + ep->len < dist[ep->v]) {
                if (inque[ep->v]) {
                    flag = true;
                    return ;
                }
                dist[ep->v] = dist[p] + ep->len;
                spfa(ep->v);
            }
        inque[p] = false;
        return ;
    }
    bool eval(void)
    {
        // Returns true if has loops of minus values
        for (int i = 1; i <= n; i++) {
            inque[i] = false;
            dist[i] = infinit;
        }
        flag = false;
        for (int i = 1; i <= n; i++) {
            dist[i] = 0;
            spfa(i);
            if (flag) return true;
        }
        return false;
    }
    void init(int n)
    {
        this->n = n;
        memset(edges, 0, sizeof(edges));
        ecnt = 0;
    }
} graph;

int F, n, m, w;

int main(int argc, char** argv)
{
    scanf("%d", &F);
    for (int idx = 1; idx <= F; idx++) {
        scanf("%d%d%d", &n, &m, &w);
        graph.init(n);
        for (int i = 1, a, b, c; i <= m; i++) {
            scanf("%d%d%d", &a, &b, &c);
            graph.addedge(a, b, c);
            graph.addedge(b, a, c);
        }
        for (int i = 1, a, b, c; i <= w; i++) {
            scanf("%d%d%d", &a, &b, &c);
            graph.addedge(a, b, -c);
        }
        bool res = graph.eval();
        printf("%s\n", res ? "YES" : "NO");
    }
    return 0;
}