Problem: AcWing 850. Dijkstra求最短路 II

思路

这是一个经典的 Dijkstra 算法问题，我们需要找到从点 1 到点 n 的最短路径。Dijkstra 算法是一种贪心算法，它总是选择当前未访问过的节点中距离最短的一个，然后更新其相邻节点的距离。

解题方法

我们使用优先队列（Java 中的 PriorityQueue）来实现 Dijkstra 算法。优先队列可以在 O(logn) 的时间复杂度内插入和删除元素，且总是保持队列头部元素是优先级最高（距离最短）的元素。首先，我们初始化所有节点的距离为无穷大（Integer.MAX_VALUE），然后将起点（节点 1）的距离设为 0，并将其加入优先队列。然后，我们开始主循环，每次从优先队列中取出一个距离最短的节点，然后遍历其所有相邻节点，如果通过当前节点到达相邻节点的距离小于相邻节点当前的距离，就更新相邻节点的距离，并将其加入优先队列。重复这个过程，直到优先队列为空。

复杂度

时间复杂度:

$O(mlogm)$，其中 m 是边的数量。这是因为每条边都会被插入优先队列一次。

空间复杂度:

$O(n+m)$，其中 n 是节点的数量，m 是边的数量。这是因为我们需要存储每个节点的距离（需要 $O(n)$ 的空间），以及图的邻接表表示（需要 $O(m)$ 的空间）。

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;public class Main {static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static StreamTokenizer sr = new StreamTokenizer(in);static int MAXN = (int) (1e5 + 10);static int MAXM = (int) (1e5 + 10);static int[] distance = new int[MAXN];static boolean[] vis = new boolean[MAXN];static ArrayList<ArrayList<int[]>> graph = new ArrayList<>();static PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[1] - b[1]);static int n, m;public static void main(String[] args) throws IOException {n = nextInt();m = nextInt();build();for (int i = 0, u, v, w; i < m; i++) {u = nextInt();v = nextInt();w = nextInt();graph.get(u).add(new int[] { v, w });}distance[1] = 0;heap.add(new int[] { 1, 0 });while (!heap.isEmpty()) {int u = heap.poll()[0];if (vis[u]) {continue;}vis[u] = true;for (int[] edge : graph.get(u)) {int v = edge[0];int w = edge[1];if (!vis[v] && distance[u] + w < distance[v]) {distance[v] = distance[u] + w;heap.add(new int[] { v, distance[v] });}}}out.println(distance[n] == Integer.MAX_VALUE ? -1 : distance[n]);out.flush();}private static void build() {// TODO Auto-generated method stubgraph.clear();for (int i = 0; i <= n; i++) {graph.add(new ArrayList<>());}heap.clear();Arrays.fill(vis, false);Arrays.fill(distance, Integer.MAX_VALUE);}static int nextInt() throws IOException {sr.nextToken();return (int) sr.nval;}}