我想在网站上卖食品怎么做,资料查询网站建设,网站建设开发语言和使用工具,谷歌排名推广公司Problem: AcWing 850. Dijkstra求最短路 II 文章目录 思路解题方法复杂度Code 思路 这是一个经典的 Dijkstra 算法问题#xff0c;我们需要找到从点 1 到点 n 的最短路径。Dijkstra 算法是一种贪心算法#xff0c;它总是选择当前未访问过的节点中距离最短的一个#xff0c;然… Problem: AcWing 850. Dijkstra求最短路 II 文章目录 思路解题方法复杂度Code 思路 这是一个经典的 Dijkstra 算法问题我们需要找到从点 1 到点 n 的最短路径。Dijkstra 算法是一种贪心算法它总是选择当前未访问过的节点中距离最短的一个然后更新其相邻节点的距离。 解题方法 我们使用优先队列Java 中的 PriorityQueue来实现 Dijkstra 算法。优先队列可以在 O(logn) 的时间复杂度内插入和删除元素且总是保持队列头部元素是优先级最高距离最短的元素。首先我们初始化所有节点的距离为无穷大Integer.MAX_VALUE然后将起点节点 1的距离设为 0并将其加入优先队列。然后我们开始主循环每次从优先队列中取出一个距离最短的节点然后遍历其所有相邻节点如果通过当前节点到达相邻节点的距离小于相邻节点当前的距离就更新相邻节点的距离并将其加入优先队列。重复这个过程直到优先队列为空。 复杂度
时间复杂度: O ( m l o g m ) O(mlogm) O(mlogm)其中 m 是边的数量。这是因为每条边都会被插入优先队列一次。 空间复杂度: O ( n m ) O(n m) O(nm)其中 n 是节点的数量m 是边的数量。这是因为我们需要存储每个节点的距离需要 O ( n ) O(n) O(n) 的空间以及图的邻接表表示需要 O ( m ) O(m) 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 ArrayListArrayListint[] graph new ArrayList();static PriorityQueueint[] 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;}}
