题目描述

blablabla

JAVA 代码

import java.util.*;
import java.io.*;

//堆优化版dijkstra算法,适合稀疏图,时间复杂度为O(mlogn);
class Main{

    static int N = 100010, n,m, idx;
    //稀疏图使用邻接表存储, 边的数目远小于点数的平方
    static int[] h = new int[N], e = new int[N], ne= new int[N];
    static int[] w = new int[N], d = new int[N];
    static boolean[] st = new boolean[N];

    static void add(int a,int b,int c){
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    static int dij(){
        Arrays.fill(d, 0x3f3f3f3f);
        d[1] = 0;
        Queue<int[]> q = new PriorityQueue<>((a,b) -> a[0]-b[0]);

        //使用堆每次选出到源点距离最小的点
        //将点到源点的距离和编号组合存入堆中
        //第一位距离, 第二位编号.
        q.offer(new int[] {0,1});
        while(!q.isEmpty()){
            int[] t = q.poll();
            //编号, 距离.
            int ver = t[1], dis = t[0];
            //改点是否获得过最短距离.
            if(st[ver]) continue;
            st[ver] = true;

            //遍历该点的邻接点
            for(int i = h[ver]; i!=-1; i = ne[i]){
                int j = e[i];
                //更新邻接点的最短距离
                if(d[j]> dis+ w[i]){
                    d[j] = dis+w[i];
                    q.offer(new int[]{d[j], j});
                }
            }

        }
        if(d[n] == 0x3f3f3f3f) return -1;
        return d[n];
    }

    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        Arrays.fill(h, -1);

        while(m-->0){
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            add(a,b,c);
        }

        System.out.println(dij());

    }
}