java模板系列之dikstra-hdu2544

HDU - 2544 https://vjudge.net/problem/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) {
            this.to = to;
            this.val = val;
        }


        @Override
        public 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.println(x.to+" "+x.val+"a");
            if(v[x.to] == true) continue;
            v[x.to] = true;
            for(int i=0;i<l[x.to].size();i++){
                int newto = l[x.to].get(i).to;
                int newval = l[x.to].get(i).val;

                if(d[x.to]+newval<d[newto]){
                    d[newto] = d[x.to]+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 = input.nextInt();
            m = input.nextInt();
            //s = input.nextInt();
            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 = input.nextInt();
                to = input.nextInt();
                val = input.nextInt();
                l[now].add(new v(to, val));
                l[to].add(new v(now, val));

            }
            dikstra();
            System.out.println(d[n]);
        }


    }




}