【一本通】虫洞

💐The Begin💐点点关注，收藏不迷路💐

John在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边，并可以使你返回到过去的一个时刻（相对你进入虫洞之前）。John的每个农场有M条小路（无向边）连接着N （从1…N标号）块地，并有W个虫洞（有向边）。其中1<=N<=500,1<=M<=2500,1<=W<=200。 现在John想借助这些虫洞来回到过去（出发时刻之前），请你告诉他能办到吗。 John将向你提供F(1<=F<=5)个农场的地图。没有小路会耗费你超过10000秒的时间，当然也没有虫洞回帮你回到超过10000秒以前。

输入

第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的地中间有一条可以使John到达T秒前的虫洞。

输出

第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

C语言代码

#include <stdio.h>
#include <stdlib.h>

#define INF 0x3f3f3f3f
#define MAXN 500 + 5

// 边结构体，存储边的起点、终点和权重（时间花费，虫洞时为负权重）
typedef struct Edge {
    int from;
    int to;
    int weight;
} Edge;

// Bellman-Ford算法判断是否存在负权环（存在负权环则能回到过去）
int bellmanFord(int n, Edge edges[], int edgeCount) {
    int dist[MAXN];
    for (int i = 1; i <= n; ++i) {
        dist[i] = INF;
    }
    dist[1] = 0;

    for (int i = 1; i <= n; ++i) {
        int updated = 0;
        for (int j = 0; j < edgeCount; ++j) {
            if (dist[edges[j].to] > dist[edges[j].from] + edges[j].weight) {
                dist[edges[j].to] = dist[edges[j].from] + edges[j].weight;
                updated = 1;
            }
        }
        if (!updated) {
            return 0;
        }
    }
    return 1;
}

int main() {
    int F;
    scanf(“%d”, &F);
    while (F–) {
        int N, M, W;
        scanf(“%d %d %d”, &N, &M, &W);

        Edge* edges = (Edge*)malloc((2  M + W)  sizeof(Edge));
        int edgeIndex = 0;
        // 读入无向边（小路）信息，转换为两条有向边存入edges
        for (int i = 0; i < M; ++i) {
            int S, E, T;
            scanf(“%d %d %d”, &S, &E, &T);
            edges[edgeIndex++] = (Edge){S, E, T};
            edges[edgeIndex++] = (Edge){E, S, T};
        }
        // 读入有向边（虫洞）信息，存入edges
        for (int i = 0; i < W; ++i) {
            int S, E, T;
            scanf(“%d %d %d”, &S, &E, &T);
            edges[edgeIndex++] = (Edge){S, E, -T};
        }

        int canGoBack = bellmanFord(N, edges, edgeIndex);
        printf(“%s\n”, canGoBack? “YES” : “NO”);

        free(edges);
    }
    return 0;
}

C++代码

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int INF = 0x3f3f3f3f;  // 定义一个很大的值，用于初始化距离等情况
const int MAXN = 500 + 5;    // 节点数量上限，题目给定范围加一些余量

// 边结构体，用于存储边的起点、终点和权重（时间花费，虫洞时为负权重）
struct Edge {
    int from;
    int to;
    int weight;
};

// 使用Bellman-Ford算法判断是否存在负权环（存在负权环则能回到过去）
bool bellmanFord(int n, vector& edges) {
    vector dist(n + 1, INF);  // 存储从源点到各节点的距离，初始化为很大值
    dist[1] = 0;  // 可以任意设置一个起始点距离为0，因为要检测整个图是否有负环

    for (int i = 1; i <= n; ++i) {  // 进行n次迭代（理论上n - 1次就够，但多一次可检测负权环）
        bool updated = false;  // 标记本轮是否有距离更新
        for (Edge edge : edges) {  // 遍历所有边
            if (dist[edge.to] > dist[edge.from] + edge.weight) {  // 尝试松弛操作
                dist[edge.to] = dist[edge.from] + edge.weight;
                updated = true;
            }
        }
        if (!updated) {  // 如果本轮没有距离更新，说明已经收敛，不存在负权环，提前退出
            return false;
        }
    }
    return true;  // 如果完成n次迭代后仍能更新距离，说明存在负权环，即能回到过去
}

int main() {
    int F;
    cin >> F;  // 读入农场个数
    while (F–) {  // 对每个农场进行处理
        int N, M, W;
        cin >> N >> M >> W;  // 读入该农场的节点数、无向边（小路）数量、有向边（虫洞）数量

        vector edges;  // 存储该农场的所有边信息
        // 读入无向边（小路）信息，将其转换为两条有向边存入edges
        for (int i = 0; i < M; ++i) {
            int S, E, T;
            cin >> S >> E >> T;
            edges.push_back({S, E, T});
            edges.push_back({E, S, T});
        }
        // 读入有向边（虫洞）信息，存入edges
        for (int i = 0; i < W; ++i) {
            int S, E, T;
            cin >> S >> E >> T;
            edges.push_back({S, E, -T});  // 虫洞权重为负，表示回到过去，时间减少
        }

        bool canGoBack = bellmanFord(N, edges);  // 判断该农场是否能回到过去
        cout << (canGoBack? “YES” : “NO”) << endl;  // 根据结果输出相应字符串
    }
    return 0;
}

JAVA代码

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

class Edge {
    int from;  // 边的起点
    int to;    // 边的终点
    int weight; // 边的权重（时间花费，虫洞时为负权重）

    public Edge(int from, int to, int weight) {
        this.from = from;
        this.to = to;
        this.weight = weight;
    }
}

public class Main {
    private static final int INF = 0x3f3f3f3f;  // 定义一个很大的值，用于初始化距离等情况
    private static final int MAXN = 500 + 5;    // 节点数量上限，题目给定范围加一些余量

    // 使用Bellman-Ford算法判断是否存在负权环（存在负权环则能回到过去）
    private static boolean bellmanFord(int n, List edges) {
        int[] dist = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dist[i] = INF;
        }
        dist[1] = 0;

        for (int i = 1; i <= n; i++) {  // 进行n次迭代（理论上n - 1次就够，但多一次可检测负权环）
            boolean updated = false;  // 标记本轮是否有距离更新
            for (Edge edge : edges) {  // 遍历所有边
                if (dist[edge.to] > dist[edge.from] + edge.weight) {  // 尝试松弛操作
                    dist[edge.to] = dist[edge.from] + edge.weight;
                    updated = true;
                }
            }
            if (!updated) {  // 如果本轮没有距离更新，说明已经收敛，不存在负权环，提前退出
                return false;
            }
        }
        return true;  // 如果完成n次迭代后仍能更新距离，说明存在负权环，即能回到过去
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int F = scanner.nextInt();  // 读入农场个数

        for (int f = 0; f < F; f++) {  // 对每个农场进行处理
            int N = scanner.nextInt();  // 读入该农场的节点数
            int M = scanner.nextInt();  // 读入该农场的无向边（小路）数量
            int W = scanner.nextInt();  // 读入该农场的有向边（虫洞）数量

            List edges = new ArrayList<>();
            // 读入无向边（小路）信息，将其转换为两条有向边存入edges
            for (int i = 0; i < M; i++) {
                int S = scanner.nextInt();
                int E = scanner.nextInt();
                int T = scanner.nextInt();
                edges.add(new Edge(S, E, T));
                edges.add(new Edge(E, S, T));
            }
            // 读入有向边（虫洞）信息，存入edges
            for (int i = 0; i < W; i++) {
                int S = scanner.nextInt();
                int E = scanner.nextInt();
                int T = scanner.nextInt();
                edges.add(new Edge(S, E, -T));  // 虫洞权重为负，表示回到过去，时间减少
            }

            boolean canGoBack = bellmanFord(N, edges);  // 判断该农场是否能回到过去
            System.out.println(canGoBack? “YES” : “NO”);  // 根据结果输出相应字符串
        }
        scanner.close();
    }
}

💐The End💐点点关注，收藏不迷路💐