day 57 图论part9

dijkstra（堆优化版）精讲 47. 参加科学大会（第六期模拟笔试）

加入小顶堆，每次从优先队列获取到最小值，不需要遍历整个数组。

importjava.util.*;classEdge{intto;intval;Edge(intto,intval){this.to=to;this.val=val;}}classPair{publicintfirst;publicintsecond;Pair(intfirst,intsecond){this.first=first;this.second=second;}}classMyComparisionimplementsComparator<Pair>{@Overridepublicintcompare(Pairr,Pairl){returnInteger.compare(r.second,l.second);}}classMain{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);intn=sc.nextInt();intm=sc.nextInt();int[]minDist=newint[n+1];List<List<Edge>>grid=newArrayList<>(n+1);Arrays.fill(minDist,Integer.MAX_VALUE);for(inti=0;i<=n;i++){grid.add(newArrayList<>());}for(inti=0;i<m;i++){ints=sc.nextInt();intt=sc.nextInt();intval=sc.nextInt();grid.get(s).add(newEdge(t,val));}boolean[]visited=newboolean[n+1];PriorityQueue<Pair>pq=newPriorityQueue<>(newMyComparision());pq.add(newPair(1,0));minDist[1]=0;while(!pq.isEmpty()){Paircur=pq.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.from=from;this.to=to;this.val=val;}}classMain{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);intn=sc.nextInt();intm=sc.nextInt();List<Edge>edges=newArrayList<>();for(inti=0;i<m;i++){ints=sc.nextInt();intt=sc.nextInt();intv=sc.nextInt();edges.add(newEdge(s,t,v));}int[]minDist=newint[n+1];Arrays.fill(minDist,Integer.MAX_VALUE);minDist[1]=0;for(inti=1;i<n;i++){for(Edgeedge:edges){if(minDist[edge.from]!=Integer.MAX_VALUE&&minDist[edge.from]+edge.val<minDist[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]);}}}