day 58 图论part10

文章目录Bellman_ford 队列优化算法又名SPFA卡码网 94. 城市间货物运输 Ibellman_ford之判断负权回路 卡码网 95. 城市间货物运输 Ibellman_ford之单源有限最短路 卡码网 96. 城市间货物运输 IIIBellman_ford 队列优化算法又名SPFA卡码网 94. 城市间货物运输 I使用队列来优化。importjava.util.*;classEdge{intto;intval;Edge(intto,intval){this.toto;this.valval;}}classMain{publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);intnsc.nextInt();intmsc.nextInt();ListListEdgegridnewArrayList();for(inti0;in;i){grid.add(newArrayList());}for(inti0;im;i){intssc.nextInt();inttsc.nextInt();intvalsc.nextInt();grid.get(s).add(newEdge(t,val));}boolean[]inquenewboolean[n1];int[]minDistnewint[n1];Arrays.fill(minDist,Integer.MAX_VALUE);minDist[1]0;QueueIntegerdqnewLinkedList();dq.add(1);inque[1]true;while(!dq.isEmpty()){intcurdq.poll();inque[cur]false;for(Edgeedge:grid.get(cur)){if(minDist[edge.to]minDist[cur]edge.val){minDist[edge.to]minDist[cur]edge.val;if(!inque[edge.to]){dq.add(edge.to);inque[edge.to]true;}}}}if(minDist[n]Integer.MAX_VALUE){System.out.println(unconnected);}else{System.out.println(minDist[n]);}}}bellman_ford之判断负权回路 卡码网 95. 城市间货物运输 I判断是否一个节点真正的入队了n次从而判断是否成环。importjava.util.*;classEdge{intto;intval;Edge(intto,intval){this.toto;this.valval;}}classMain{publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);intnsc.nextInt();intmsc.nextInt();ListListEdgegridnewArrayList();for(inti0;in;i){grid.add(newArrayList());}for(inti0;im;i){intssc.nextInt();inttsc.nextInt();intvalsc.nextInt();grid.get(s).add(newEdge(t,val));}boolean[]inquenewboolean[n1];int[]minDistnewint[n1];Arrays.fill(minDist,Integer.MAX_VALUE);minDist[1]0;QueueIntegerdqnewLinkedList();dq.add(1);inque[1]true;booleanflagfalse;int[]countnewint[n1];while(!dq.isEmpty()){intcurdq.poll();inque[cur]false;for(Edgeedge:grid.get(cur)){if(minDist[edge.to]minDist[cur]edge.val){minDist[edge.to]minDist[cur]edge.val;if(!inque[edge.to]){dq.add(edge.to);inque[edge.to]true;count[edge.to];}if(count[edge.to]n){flagtrue;while(!dq.isEmpty())dq.poll();break;}}}}if(flag){System.out.println(circle);}elseif(minDist[n]Integer.MAX_VALUE){System.out.println(unconnected);}else{System.out.println(minDist[n]);}}}bellman_ford之单源有限最短路 卡码网 96. 城市间货物运输 III从原点开始松弛边松弛一次能找到距离原点1条边的最短路径k个点就需要松弛k 1边。importjava.util.*;classEdge{intfrom;intto;intval;Edge(intfrom,intto,intval){this.fromfrom;this.toto;this.valval;}}classMain{publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);intnsc.nextInt();intmsc.nextInt();ListEdgegridnewArrayList();for(inti0;im;i){intssc.nextInt();inttsc.nextInt();intvalsc.nextInt();grid.add(newEdge(s,t,val));}intsrcsc.nextInt();intdstsc.nextInt();intksc.nextInt();int[]minDistnewint[n1];Arrays.fill(minDist,Integer.MAX_VALUE);int[]copyDistnewint[n1];minDist[src]0;for(inti0;ik1;i){copyDistArrays.copyOf(minDist,n1);for(Edgeedge:grid){if(copyDist[edge.from]!Integer.MAX_VALUEminDist[edge.to]copyDist[edge.from]edge.val){minDist[edge.to]copyDist[edge.from]edge.val;}}}if(minDist[dst]Integer.MAX_VALUE){System.out.println(unreachable);}else{System.out.println(minDist[dst]);}}}