最短路径

#最短路径| 来源: 网络整理| 查看: 265

问题要素思路模板

问题

解决这样一类问题，起点确定的，可以有重边和自环的，各边权都为正数的稀疏图的最短路问题

要素 h[], idx, e[], ne[], w[] 用邻接表存储图st[]记录已经确定最短距离的点dist[] 存储每个点到起点的最短距离思路相较与朴素版Dijkstra每次遍历一遍所有节点找到当前距起点最近的点，堆优化版优化了这一做法，有点类似bfs，每次的队头元素如果还没加入st的话，一定是当前距起点最近的点，用该点更新其临点到起点的距离并入队，因为是优先队列，每次加入一个元素会更新队列使得最小元素出现在队头。

时间复杂度：手写堆：O(M*logN)，优先队列：O(M*logM) = O(MlogN2) = O(MlogN)所以没必要手写堆本质：贪心

模板

850. Dijkstra求最短路 II给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为非负值。请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n号点，则输出 −1。输入格式第一行包含整数 n和 m。接下来 m行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y的有向边，边长为 z。输出格式输出一个整数，表示 1号点到 n 号点的最短距离。如果路径不存在，则输出 −1。数据范围1≤n,m≤1.5×105图中涉及边长均不小于 0，且不超过 10000。输入样例：

3 31 2 22 3 11 3 4

输出样例：

3import java.util.*;public class Main { static final int N = 150010; static int[] h = new int[N], e = new int[N], ne = new int[N], w = new int[N]; static int[] dist = new int[N]; static boolean[] st = new boolean[N]; static int n, m; static int idx = 0; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); Arrays.fill(h, -1); for (int i = 0; i (o1[1] - o2[1])); q.offer(new int[]{start, 0}); while (!q.isEmpty()) { int[] p = q.poll(); int u = p[0], d = p[1]; if (st[u]) continue; st[u] = true; dist[u] = d; for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i], ww = w[i]; q.offer(new int[]{j, ww + d}); } } } static void add(int a, int b, int c) { e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx++; }}

【本文地址】

最短路径

最短路径

今日新闻

推荐新闻