Day60 ＞＞ 94、城市间货物运输1️⃣ + 95、城市间货物运输 2️⃣ + 96、城市间货物运输 3️⃣

代码随想录-图论Part10

94、城市间货物运输 1️⃣

Bellman_ford队列优化算法

import java.util.*; public class Main { // Define an inner class Edge static class Edge { int from; int to; int val; public Edge(int from, int to, int val) { this.from = from; this.to = to; this.val = val; } } public static void main(String[] args) { // Input processing Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); List<List<Edge>> graph = new ArrayList<>(); for (int i = 0; i <= n; i++) { graph.add(new ArrayList<>()); } for (int i = 0; i < m; i++) { int from = sc.nextInt(); int to = sc.nextInt(); int val = sc.nextInt(); graph.get(from).add(new Edge(from, to, val)); } // Declare the minDist array to record the minimum distance form current node to the original node int[] minDist = new int[n + 1]; Arrays.fill(minDist, Integer.MAX_VALUE); minDist[1] = 0; // Declare a queue to store the updated nodes instead of traversing all nodes each loop for more efficiency Queue<Integer> queue = new LinkedList<>(); queue.offer(1); // Declare a boolean array to record if the current node is in the queue to optimise the processing boolean[] isInQueue = new boolean[n + 1]; while (!queue.isEmpty()) { int curNode = queue.poll(); isInQueue[curNode] = false; // Represents the current node is not in the queue after being polled for (Edge edge : graph.get(curNode)) { if (minDist[edge.to] > minDist[edge.from] + edge.val) { // Start relaxing the edge minDist[edge.to] = minDist[edge.from] + edge.val; if (!isInQueue[edge.to]) { // Don't add the node if it's already in the queue queue.offer(edge.to); isInQueue[edge.to] = true; } } } } // Outcome printing if (minDist[n] == Integer.MAX_VALUE) { System.out.println("unconnected"); } else { System.out.println(minDist[n]); } } }

95、城市间货物运输 2️⃣

Bellman_ford判断负权回路

import java.util.*; public class Main { // 基于Bellman_ford-SPFA方法 // Define an inner class Edge static class Edge { int from; int to; int val; public Edge(int from, int to, int val) { this.from = from; this.to = to; this.val = val; } } public static void main(String[] args) { // Input processing Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); List<List<Edge>> graph = new ArrayList<>(); for (int i = 0; i <= n; i++) { graph.add(new ArrayList<>()); } for (int i = 0; i < m; i++) { int from = sc.nextInt(); int to = sc.nextInt(); int val = sc.nextInt(); graph.get(from).add(new Edge(from, to, val)); } // Declare the minDist array to record the minimum distance form current node to the original node int[] minDist = new int[n + 1]; Arrays.fill(minDist, Integer.MAX_VALUE); minDist[1] = 0; // Declare a queue to store the updated nodes instead of traversing all nodes each loop for more efficiency Queue<Integer> queue = new LinkedList<>(); queue.offer(1); // Declare an array to record the times each node has been offered in the queue int[] count = new int[n + 1]; count[1]++; // Declare a boolean array to record if the current node is in the queue to optimise the processing boolean[] isInQueue = new boolean[n + 1]; // Declare a boolean value to check if there is a negative weight loop inside the graph boolean flag = false; while (!queue.isEmpty()) { int curNode = queue.poll(); isInQueue[curNode] = false; // Represents the current node is not in the queue after being polled for (Edge edge : graph.get(curNode)) { if (minDist[edge.to] > minDist[edge.from] + edge.val) { // Start relaxing the edge minDist[edge.to] = minDist[edge.from] + edge.val; if (!isInQueue[edge.to]) { // Don't add the node if it's already in the queue queue.offer(edge.to); count[edge.to]++; isInQueue[edge.to] = true; } if (count[edge.to] == n) { // If some node has been offered in the queue more than n-1 times flag = true; while (!queue.isEmpty()) queue.poll(); break; } } } } if (flag) { System.out.println("circle"); } else if (minDist[n] == Integer.MAX_VALUE) { System.out.println("unconnected"); } else { System.out.println(minDist[n]); } } }

96、城市间货物运输 3️⃣

Bellman_ford单源有限最短路

import java.util.*; public class Main { // 基于Bellman_for一般解法解决单源最短路径问题 // Define an inner class Edge static class Edge { int from; int to; int val; public Edge(int from, int to, int val) { this.from = from; this.to = to; this.val = val; } } public static void main(String[] args) { // Input processing Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); List<Edge> graph = new ArrayList<>(); for (int i = 0; i < m; i++) { int from = sc.nextInt(); int to = sc.nextInt(); int val = sc.nextInt(); graph.add(new Edge(from, to, val)); } int src = sc.nextInt(); int dst = sc.nextInt(); int k = sc.nextInt(); int[] minDist = new int[n + 1]; int[] minDistCopy; Arrays.fill(minDist, Integer.MAX_VALUE); minDist[src] = 0; for (int i = 0; i < k + 1; i++) { // Relax all edges k + 1 times minDistCopy = Arrays.copyOf(minDist, n + 1); for (Edge edge : graph) { int from = edge.from; int to = edge.to; int val = edge.val; // Use minDistCopy to calculate minDist if (minDistCopy[from] != Integer.MAX_VALUE && minDist[to] > minDistCopy[from] + val) { minDist[to] = minDistCopy[from] + val; } } } // Output printing if (minDist[dst] == Integer.MAX_VALUE) { System.out.println("unreachable"); } else { System.out.println(minDist[dst]); } } }