【Dijkstra算法】最短距离

题目

1488. 最短距离 - AcWing题库

有 $N$ 个村庄，编号 $1$ 到 $N$ 。

村庄之间有 $M$ 条无向道路，第 $i$ 条道路连接村庄 $a_i$ 和村庄 $b_i$ ，长度是 $c_i$ 。

所有村庄都是连通的。

共有 $K$ 个村庄有商店，第 $j$ 个有商店的村庄编号是 $x_j$ 。

然后给出 $Q$ 个询问，第 $k$ 个询问给出一个村庄的编号 $y_k$ ，问该村庄距离最近的商店有多远？

输入格式

第一行包含两个整数 $N,M$ 。

接下来 $M$ 行，每行包含三个整数 $a_i,b_i,c_i$ ，表示第 $i$ 条道路连接村庄 $a_i$ 和村庄 $b_i$ ，长度是 $c_i$ 。

再一行包含整数 $K$ 。

接下来 $K$ 行，每行包含一个整数 $x_j$ ，表示第 $j$ 个有商店的村庄编号是 $x_j$ 。

再一行包含整数 $Q$ 。

接下来 $Q$ 行，每行包含一个整数 $y_k$ ，表示询问编号为 $y_k$ 的村庄与其距离最近的商店之间的距离。

输出格式

对于每个询问，输出该询问的结果。

数据范围

$2 \le N \le 10^5$ ,
$N-1 \le M \le min(\frac{N(N-1)}{2},10^5)$ ,
$1 \le Q \le 10^5$ ,
$1 \le K \le N$ ,
$1 \le c_i \le 10000$

输入样例：

输出样例：

解题

方法一：Dijkstra 算法

思路

对于某一村庄顶点 $S_t$ ，设其可以到达的 $k$ 个有商店的村庄顶点（以下简称为商店顶点）分别为 $S_1, S_2, \dots, S_k$ ，那么 $S_t$ 到商店节点的路径集合为 $A = \{{S_t \to S_1}, {S_t \to S_k}, \dots, {S_t \to S_k}\}$ ，那么 $S_t$ 到与其最近商店之间距离为 $\min(A)$ ，到这里直接做的话，对于每个村庄节点都要求 $k$ 次最短路再取最小，显然会超时，所以需要转换。

构造一个虚拟源点 $S_s$ ，把所有商店顶点和该虚拟源点之间连一条权值为 $0$ 的通路，那么 $S_s$ 到 $S_t$ 的路径集合为 $B = \{{S_s \to S_1 \to S_t}, {S_s \to S_2 \to S_t}, \dots, {S_s \to S_k \to S_t}\}$ （由于 $S_s$ 只与商店顶点有通路，所以从 $S_s$ 到任意一个村庄节点都必至少经过一个商店顶点）。

此时： $\forall{x \in A}, \exists{x' \in B} \,\, \text{s.t.} \,\, d_x = d_{x'}$ ，同理： $\forall{x \in B}, \exists{x' \in A} \,\, \text{s.t.} \,\, d_x = d_{x'}$ ，所以 $A = B$ ，那么 $\min(A) = \min(B)$ 。

此时问题就变成了一个最朴素的单源最短路问题，只要求一遍 $S_s$ 到所有村庄节点的最短路然后对每个村庄节点在 dists 数组里取最短距离即可。

本题没有负权边，且是一个稠密图，所以使用堆优化版Dijkstra算法求解。

代码

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

public class Main {
    static final int INF = 0x3f3f3f3f;
    static int n, m;
    static int[] h, e, ne, w;
    static int idx;
    static int k;
    static int[] dists;
    static boolean[] vis;
    static Queue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    
    static void dijkstra() {
        Arrays.fill(dists, INF);
        dists[0] = 0;
        pq.offer(new int[]{0, 0});
        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int d = curr[0], mn = curr[1];
            if (vis[mn]) continue;
            for (int i = h[mn]; i != -1; i = ne[i]) {
                int v = e[i];
                if (d + w[i] < dists[v]) {
                    dists[v] = d + w[i];
                    pq.offer(new int[]{dists[v], v});
                }
            }
        }
    }
    
    static void add(int a, int b, int c) {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        n = (int) in.nval;
        in.nextToken();
        m = (int) in.nval;
        h = new int[n + 1];
        e = new int[m * 2 + 2 * n];
        ne = new int[m * 2 + 2 * n];
        w = new int[m * 2 + 2 * n];
        dists = new int[n + 1];
        vis = new boolean[n + 1];
        Arrays.fill(h, -1);
        while (m-- > 0) {
            in.nextToken();
            int x = (int) in.nval;
            in.nextToken();
            int y = (int) in.nval;
            in.nextToken();
            int z = (int) in.nval;
            add(x, y, z);
            add(y, x, z);
        }
        in.nextToken();
        k = (int) in.nval;
        for (int i = 0; i < k; ++i) {
            in.nextToken();
            int x = (int) in.nval;
            add(x, 0, 0);
            add(0, x, 0);
        }
        dijkstra();
        in.nextToken();
        int q = (int) in.nval;
        while (q-- > 0) {
            in.nextToken();
            int y = (int) in.nval;
            System.out.println(dists[y]);
        }
    }
}

目录CONTENT

【Dijkstra算法】最短距离

题目

解题

方法一：Dijkstra 算法

思路

代码

评论区