题解 | 小红送外卖

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] parts = br.readLine().split(" ");
        int n = Integer.parseInt(parts[0]);
        int m = Integer.parseInt(parts[1]);
        int q = Integer.parseInt(parts[2]);

        // 构建邻接表
        List<int[]>[] graph = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int i = 0; i < m; i++) {
            parts = br.readLine().split(" ");
            int u = Integer.parseInt(parts[0]);
            int v = Integer.parseInt(parts[1]);
            int w = Integer.parseInt(parts[2]);
            graph[u].add(new int[] {v, w});
            graph[v].add(new int[] {u, w});
        }

        // Dijkstra算法计算最短路径
        long[] dist = new long[n + 1];
        Arrays.fill(dist, Long.MAX_VALUE);
        dist[1] = 0;
        PriorityQueue<long[]> heap = new PriorityQueue<>(Comparator.comparingLong(
                    a -> a[0]));
        heap.offer(new long[] {0, 1});

        while (!heap.isEmpty()) {
            long[] current = heap.poll();
            long d = current[0];
            int u = (int) current[1];
            if (d > dist[u]) {
                continue;
            }
            for (int[] edge : graph[u]) {
                int v = edge[0];
                int w = edge[1];
                if (dist[v] > d + w) {
                    dist[v] = d + w;
                    heap.offer(new long[] {dist[v], v});
                }
            }
        }

        // 统计每个学校出现的次数
        int[] count = new int[n + 1];
        parts = br.readLine().split(" ");
        for (int i = 0; i < q; i++) {
            int a = Integer.parseInt(parts[i]);
            count[a]++;
        }

        // 计算总距离
        long sum = 0;
        for (int i = 2; i <= n; i++) {
            if (count[i] > 0) {
                sum += (long) count[i] * 2 * dist[i];
            }
        }
        System.out.println(sum);
    }
}

https://www.nowcoder.com/discuss/727521113110073344

思路：

1. 输入处理：使用BufferedReader读取输入数据，构建邻接表表示图的边。
2. Dijkstra算法：通过优先队列优化最短路径计算，从美食街（1号结点）出发，计算到各个学校的最短路径。
3. 统计订单次数：记录每个学校的外卖订单次数。
4. 总距离计算：根据每个学校的订单次数和最短路径，计算总骑行距离并输出结果。