DAY60Bellman_ford 算法

队列优化算法

请找出从城市 1 到城市 n 的所有可能路径中，综合政府补贴后的最低运输成本。
如果能够从城市 1 到连通到城市 n， 请输出一个整数，表示运输成本。如果该整数是负数，则表示实现了盈利。如果从城市 1 没有路径可达城市 n，请输出 “unconnected”。

import java.util.*;public class Test {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) {Scanner in=new Scanner(System.in);int n=in.nextInt();int m=in.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=in.nextInt();int to=in.nextInt();int val=in.nextInt();graph.get(from).add(new Edge(from, to, val));}int[]minDist=new int[n+1];Arrays.fill(minDist,Integer.MAX_VALUE);minDist[1]=0;Queue<Integer> queue=new LinkedList<>();queue.offer(1);boolean[] isInQueue=new boolean[n+1];while(!queue.isEmpty()){int curNode=queue.poll();isInQueue[curNode]=false;for(Edge edge:graph.get(curNode)){if(minDist[edge.to]>minDist[edge.from]+edge.val){minDist[edge.to]=minDist[edge.from]+edge.val;if(!isInQueue[edge.to]){queue.offer(edge.to);isInQueue[edge.to]=true;}}}}if(minDist[n]==Integer.MAX_VALUE){System.out.println("unconnected");}else{System.out.println(minDist[n]);}}}

判断负权回路

负权回路是指一系列道路的总权值为负，这样的回路使得通过反复经过回路中的道路，理论上可以无限地减少总成本或无限地增加总收益。
请找出从城市 1 到城市 n 的所有可能路径中，综合政府补贴后的最低运输成本。同时能够检测并适当处理负权回路的存在。

import java.util.*;public class Test {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) {Scanner in=new Scanner(System.in);int n=in.nextInt();int m=in.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=in.nextInt();int to=in.nextInt();int val=in.nextInt();graph.get(from).add(new Edge(from, to, val));}int[]minDist=new int[n+1];Arrays.fill(minDist,Integer.MAX_VALUE);minDist[1]=0;Queue<Integer> queue=new LinkedList<>();queue.offer(1);boolean[] isInQueue=new boolean[n+1];int[] count=new int[n+1];count[1]++;boolean flag=false;while(!queue.isEmpty()){int curNode=queue.poll();isInQueue[curNode]=false;for(Edge edge:graph.get(curNode)){if(minDist[edge.to]>minDist[edge.from]+edge.val){minDist[edge.to]=minDist[edge.from]+edge.val;if(!isInQueue[edge.to]){queue.offer(edge.to);count[edge.to]++;isInQueue[edge.to]=true;}if(count[edge.to]==n){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]);}}}

加了一个count数组，若松弛 n 次以上，则存在负权回路

单源有限最短路

某国为促进城市间经济交流，决定对货物运输提供补贴。共有 n 个编号为 1 到 n 的城市，通过道路网络连接，网络中的道路仅允许从某个城市单向通行到另一个城市，不能反向通行。

网络中的道路都有各自的运输成本和政府补贴，道路的权值计算方式为：运输成本 - 政府补贴。

权值为正表示扣除了政府补贴后运输货物仍需支付的费用；

权值为负则表示政府的补贴超过了支出的运输成本，实际表现为运输过程中还能赚取一定的收益。

请计算在最多经过 k 个城市的条件下，从城市 src 到城市 dst 的最低运输成本

import java.util.*;public class Main {// 基于Bellman_for一般解法解决单源最短路径问题// Define an inner class Edgestatic 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 processingScanner 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 timesminDistCopy = 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 minDistif (minDistCopy[from] != Integer.MAX_VALUE && minDist[to] > minDistCopy[from] + val) {minDist[to] = minDistCopy[from] + val;}}}// Output printingif (minDist[dst] == Integer.MAX_VALUE) {System.out.println("unreachable");} else {System.out.println(minDist[dst]);}}
}