day 57 图论part9

文章目录dijkstra堆优化版精讲 47. 参加科学大会第六期模拟笔试Bellman_ford 算法精讲 94. 城市间货物运输 Idijkstra堆优化版精讲 47. 参加科学大会第六期模拟笔试加入小顶堆每次从优先队列获取到最小值不需要遍历整个数组。importjava.util.*;classEdge{intto;intval;Edge(intto,intval){this.toto;this.valval;}}classPair{publicintfirst;publicintsecond;Pair(intfirst,intsecond){this.firstfirst;this.secondsecond;}}classMyComparisionimplementsComparatorPair{Overridepublicintcompare(Pairr,Pairl){returnInteger.compare(r.second,l.second);}}classMain{publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);intnsc.nextInt();intmsc.nextInt();int[]minDistnewint[n1];ListListEdgegridnewArrayList(n1);Arrays.fill(minDist,Integer.MAX_VALUE);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[]visitednewboolean[n1];PriorityQueuePairpqnewPriorityQueue(newMyComparision());pq.add(newPair(1,0));minDist[1]0;while(!pq.isEmpty()){Paircurpq.poll();visited[cur.first]true;for(Edgeedge:grid.get(cur.first)){if(!visited[edge.to]minDist[edge.to]minDist[cur.first]edge.val){minDist[edge.to]minDist[cur.first]edge.val;pq.add(newPair(edge.to,minDist[edge.to]));}}}if(minDist[n]Integer.MAX_VALUE){System.out.println(-1);}else{System.out.println(minDist[n]);}}}Bellman_ford 算法精讲 94. 城市间货物运输 I总共最多需要松弛边n - 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();ListEdgeedgesnewArrayList();for(inti0;im;i){intssc.nextInt();inttsc.nextInt();intvsc.nextInt();edges.add(newEdge(s,t,v));}int[]minDistnewint[n1];Arrays.fill(minDist,Integer.MAX_VALUE);minDist[1]0;for(inti1;in;i){for(Edgeedge:edges){if(minDist[edge.from]!Integer.MAX_VALUEminDist[edge.from]edge.valminDist[edge.to]){minDist[edge.to]minDist[edge.from]edge.val;}}}if(minDist[n]Integer.MAX_VALUE){System.out.println(unconnected);}else{System.out.println(minDist[n]);}}}