Java 输入数据很多 使用快读

多源，其实就是起点从一个换到多个，也就是队列初始时有多个元素
其余操作与普通BFS没差

以所有分店为起点，逐级遍历并保存能到达某格的最短距离，最后把客户位置所在的订单数量乘上分店们到达该格的最短距离得到完成本位置订单所需的代价

遍历过程中，首次到达某个客户位置的一定就是最短路，所以并不需要遍历完所有格子再计算总代价
可以事先记录下客户所在的不重复位置个数，并在遍历时保存当前格子的最短距离，若恰好遍历到客户位置，就计算代价并更新所剩客户位置数量，解决完所有客户即可退出

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.lang.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    static class Point {
        int x, y, w;

        public Point(int x, int y, int w) {
            this.x = x;
            this.y = y;
            this.w = w;
        }
    }

    static int n, m, k, d, N = 1010;
    static int[][] f = new int[N][N];
    static int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        // 快读 输入数据量过多 Scanner超时
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        LinkedList<Point> list = new LinkedList<>();
        String[] ss = reader.readLine().split(" ");
        n = Integer.parseInt(ss[0]);
        m = Integer.parseInt(ss[1]);
        k = Integer.parseInt(ss[2]);
        d = Integer.parseInt(ss[3]);
        for (int i = 1, x, y; i <= m; i++) {  // 读分店 存所有分店入队列 初始距离记为0
            String[] s = reader.readLine().split(" ");
            x = Integer.parseInt(s[0]);
            y = Integer.parseInt(s[1]);
            list.add(new Point(x, y, 0));
            f[x][y] = -1;
        }
        int cnt = 0;
        for (int i = 1, x, y, c; i <= k; i++) {  // 存订单
            String[] s = reader.readLine().split(" ");
            x = Integer.parseInt(s[0]);
            y = Integer.parseInt(s[1]);
            c = Integer.parseInt(s[2]);
            if (f[x][y] == 0) cnt++;  // 记录坐标不重复的订单数量
            f[x][y] += c;  // 考虑同一位置多个订单  所以 +=
        }
        for (int i = 1, x, y; i <= d; i++) {
            String[] s = reader.readLine().split(" ");
            x = Integer.parseInt(s[0]);
            y = Integer.parseInt(s[1]);
            f[x][y] = -1;  // 障碍位置 初始标记已开发
        }
        long sum = 0;
        while (!list.isEmpty() && cnt > 0) {  // 没有遍历完 且 还有订单待解决
            Point p = list.removeFirst();
            for (int i = 0; i < 4; i++) {
                int x = p.x + dx[i], y = p.y + dy[i], w = p.w + 1;  // 下一个坐标及其距离
                if (x >= 1 && x <= n && y >= 1 && y <= n && f[x][y] >= 0) {
                    if (f[x][y] > 0) {  // >0 说明有订单
                        sum += w * f[x][y];  // 计算代价 距离*餐数
                        cnt--;  // 订单-1
                    }
                    list.add(new Point(x, y, w));
                    f[x][y] = -1;  // 标记已开发
                }
            }
        }
        System.out.println(sum);
    }
}