题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.*;


public class Main {
    static int N = 150010;
    static int n;
//e表示当前点沿着边到达的终点
//w表示权重
//ne表示同一个a下是否存好几个终点，-1表示不存在，其他值表示下一终点的角标
//h存的起点h[a] 表示从点a出发，这条边信息存储的角标。通过角标可以知道，终点以及权重
    static int[] h = new int[N];
    static int[] e = new int[N];
    static int[] ne = new int[N];
    static int[] w = new int[N];
    static int index = 0;
    static int[] dist = new int[N];// 存储1号点到每个点的最短距离
    static boolean[] st = new boolean[N];

    public static void add(int a, int b, int c) {
        e[index]=b;
        w[index]=c;
        ne[index]=h[a];
        h[a]=index++;
    }

    // 求1号点到n号点的最短路，如果不存在则返回-1
    public int dijkstra() {
        //设置无穷大
        int INF = 0x3f3f3f3f;
        Arrays.fill(dist, INF);
        dist[1]=0;
        PriorityQueue<Pair> queue=new PriorityQueue<>();
        queue.add(new Pair(0,1));
        while (!queue.isEmpty()){
            Pair temp=queue.poll();
            int t=temp.getSecond();
            int distance=temp.getFirst();
            if (st[t])
                continue;
            st[t]=true;
            for (int i = h[t]; i !=-1 ; i=ne[i]) {
            //对于t出发的所有边进行遍历更新dist
                int j=e[i];
                dist[j]=Math.min(distance+w[i],dist[j]);
                queue.add(new Pair(dist[j],j));
            }
        }
        if (dist[n]== INF)
            return -1;
        return dist[n];


    }

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

        while (m-- > 0) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            add(a, b, c);
        }
        System.out.println(new Main().dijkstra());
    }
}


class Pair implements Comparable<Pair> {
    private int first;
    private int second;

    Pair(int first, int second) {
        this.first = first;
        this.second = second;
    }

    @Override
    public int compareTo(Pair o) {
        return first-o.first;
    }

    public int getFirst() {
        return first;
    }

    public int getSecond() {
        return second;
    }
}