wordpress指定目录文章,一键优化大师,犀牛网站建设,网页制作与网站建设期末考试队列优化算法
请找出从城市 1 到城市 n 的所有可能路径中#xff0c;综合政府补贴后的最低运输成本。 如果能够从城市 1 到连通到城市 n#xff0c; 请输出一个整数#xff0c;表示运输成本。如果该整数是负数#xff0c;则表示实现了盈利。如果从城市 1 没有路径可达城市…队列优化算法
请找出从城市 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.fromfrom;this.toto;this.valval;}}public static void main(String[] args) {Scanner innew Scanner(System.in);int nin.nextInt();int min.nextInt();ListListEdge graphnew ArrayList();for(int i0;in;i){graph.add(new ArrayList());}for(int i0;im;i){int fromin.nextInt();int toin.nextInt();int valin.nextInt();graph.get(from).add(new Edge(from, to, val));}int[]minDistnew int[n1];Arrays.fill(minDist,Integer.MAX_VALUE);minDist[1]0;QueueInteger queuenew LinkedList();queue.offer(1);boolean[] isInQueuenew boolean[n1];while(!queue.isEmpty()){int curNodequeue.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.fromfrom;this.toto;this.valval;}}public static void main(String[] args) {Scanner innew Scanner(System.in);int nin.nextInt();int min.nextInt();ListListEdge graphnew ArrayList();for(int i0;in;i){graph.add(new ArrayList());}for(int i0;im;i){int fromin.nextInt();int toin.nextInt();int valin.nextInt();graph.get(from).add(new Edge(from, to, val));}int[]minDistnew int[n1];Arrays.fill(minDist,Integer.MAX_VALUE);minDist[1]0;QueueInteger queuenew LinkedList();queue.offer(1);boolean[] isInQueuenew boolean[n1];int[] countnew int[n1];count[1];boolean flagfalse;while(!queue.isEmpty()){int curNodequeue.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){flagtrue;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();ListEdge 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]);}}
}
