【一本通】虫洞
【一本通】虫洞
- C语言代码
- C++代码
- JAVA代码
| 💐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💐点点关注，收藏不迷路💐 |