公司网站邮箱费用,网站开发 重庆,做网站销售工资怎么样,番禺网站开发技术【一本通】虫洞 C语言代码C代码JAVA代码 #x1f490;The Begin#x1f490;点点关注#xff0c;收藏不迷路#x1f490; John在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边#xff0c;并可以使你返回到过去的一个时刻#xff08;相对你进入虫洞之… 【一本通】虫洞 C语言代码C代码JAVA代码 The Begin点点关注收藏不迷路
John在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边并可以使你返回到过去的一个时刻相对你进入虫洞之前。John的每个农场有M条小路无向边连接着N 从1…N标号块地并有W个虫洞有向边。其中1N500,1M2500,1W200。 现在John想借助这些虫洞来回到过去出发时刻之前请你告诉他能办到吗。 John将向你提供F(1F5)个农场的地图。没有小路会耗费你超过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
YESC语言代码
#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点点关注收藏不迷路
