java模板系列之dikstra

java模板系列之dikstra

HDU - 2544

没有什么太多好说的，优先队列优化的dikstra，时间复杂度可近似看为mlogn，m为边，n为点

//
// Source code recreated from a .class file by IntelliJ IDEA
// (powered by FernFlower decompiler)
//import java.util.*;public class Main {//既代表了list中的边权和终点，也代表了优先队列中的点和到达该点的最小权值static class v implements Comparable<v>{int to;int val;public v(int to, int val) { = to;this.val = val;}@Overridepublic int compareTo(v o) {return this.val - o.val;}}static void dikstra(){PriorityQueue<v> q = new PriorityQueue<v>();Arrays.fill(v,false);Arrays.fill(d,1000000009);d[1] = 0;q.add(new v(1,0));while(q.size() > 0){v x = q.poll();//System.out.+" "+x.val+"a");if(] == true) continue;] = true;for(int i=0;i<].size();i++){int newto = ].get(i).to;int newval = ].get(i).val;if(]+newval<d[newto]){d[newto] = ]+newval;q.add(new v(newto,d[newto]));}}}}static int d[];static boolean v[];static int n,m,s;static List<v> l[];public static void main(String[] args) {Scanner input = new Scanner(System.in);while(input.hasNextInt()) {n = Int();m = Int();//s = Int();if(n==0&&m==0) break;d = new int[n + 1];v = new boolean[n + 1];l = new List[n + 1];for (int i = 1; i <= n; i++) {l[i] = new ArrayList<v>();}for (int i = 0; i < m; i++) {int now, to, val;now = Int();to = Int();val = Int();l[now].add(new v(to, val));l[to].add(new v(now, val));}dikstra();System.out.println(d[n]);}}}