侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【Dijkstra算法】最短距离

GabrielxD
2023-03-05 / 0 评论 / 0 点赞 / 155 阅读 / 1,376 字
温馨提示:
本文最后更新于 2023-03-05,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

1488. 最短距离 - AcWing题库


NN 个村庄,编号 11NN

村庄之间有 MM无向道路,第 ii 条道路连接村庄 aia_i 和村庄 bib_i ,长度是 cic_i

所有村庄都是连通的。

共有 KK 个村庄有商店,第 jj 个有商店的村庄编号是 xjx_j

然后给出 QQ 个询问,第 kk 个询问给出一个村庄的编号 yky_k ,问该村庄距离最近的商店有多远?

输入格式

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

接下来 MM 行,每行包含三个整数 ai,bi,cia_i,b_i,c_i ,表示第 ii 条道路连接村庄 aia_i 和村庄 bib_i ,长度是 cic_i

再一行包含整数 KK

接下来 KK 行,每行包含一个整数 xjx_j ,表示第 jj 个有商店的村庄编号是 xjx_j

再一行包含整数 QQ

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

输出格式

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

数据范围

2N1052 \le N \le 10^5 ,
N1Mmin(N(N1)2,105)N-1 \le M \le min(\frac{N(N-1)}{2},10^5) ,
1Q1051 \le Q \le 10^5 ,
1KN1 \le K \le N ,
1ci100001 \le c_i \le 10000

输入样例:

7 7
1 2 5
1 4 3
2 3 2
2 5 1
3 6 7
5 6 8
6 7 6
3
7
5
4
7
1
2
3
4
5
6
7

输出样例:

3
1
3
0
0
6
0

解题

方法一:Dijkstra 算法

思路

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

构造一个虚拟源点 SsS_s ,把所有商店顶点和该虚拟源点之间连一条权值为 00 的通路,那么 SsS_sStS_t 的路径集合为 B={SsS1St,SsS2St,,SsSkSt}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}\} (由于 SsS_s 只与商店顶点有通路,所以从 SsS_s 到任意一个村庄节点都必至少经过一个商店顶点)。

此时: xA,xBs.t.dx=dx\forall{x \in A}, \exists{x' \in B} \,\, \text{s.t.} \,\, d_x = d_{x'} ,同理:xB,xAs.t.dx=dx\forall{x \in B}, \exists{x' \in A} \,\, \text{s.t.} \,\, d_x = d_{x'} ,所以 A=BA = B ,那么 min(A)=min(B)\min(A) = \min(B)

此时问题就变成了一个最朴素的单源最短路问题,只要求一遍 SsS_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]);
        }
    }
}
0

评论区