最优配餐

形式化题目

给定 $n\times n$ 方格图，格点上有 $m$ 个分店、 $k$ 个客户（需求量 $c_i$ ）和 $d$ 个不可经过的障碍。相邻格点距离为 1，任意分店可配送任意客户，求 $\sum c_i \times \text{距离}$ 的最小值。

思路

先看对每个客户单独 BFS 的暴力：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:55
 */
// brute.cpp：小数据暴力解，对每个客户单独 BFS 到最近分店。
#include <bits/stdc++.h>
using namespace std;

struct Customer {
    int x;
    int y;
    int amount;
};

int n;
vector<pair<int, int> > stores;
vector<vector<bool> > blocked;

int shortest_distance(int start_x, int start_y) {
    const int INF = 0x3f3f3f3f;
    vector<vector<int> > dist(n + 1, vector<int>(n + 1, INF));
    queue<pair<int, int> > q;
    dist[start_x][start_y] = 0;
    q.push(make_pair(start_x, start_y));

    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};
    while (!q.empty()) {
        pair<int, int> current = q.front();
        q.pop();
        for (int i = 0; i < (int)stores.size(); i++) {
            if (current.first == stores[i].first && current.second == stores[i].second) {
                return dist[current.first][current.second];
            }
        }

        for (int dir = 0; dir < 4; dir++) {
            int nx = current.first + dx[dir];
            int ny = current.second + dy[dir];
            if (nx < 1 || nx > n || ny < 1 || ny > n) {
                continue;
            }
            if (blocked[nx][ny] || dist[nx][ny] != INF) {
                continue;
            }
            dist[nx][ny] = dist[current.first][current.second] + 1;
            q.push(make_pair(nx, ny));
        }
    }
    return INF;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int m, k, d;
    cin >> n >> m >> k >> d;

    stores.resize(m);
    for (int i = 0; i < m; i++) {
        cin >> stores[i].first >> stores[i].second;
    }

    vector<Customer> customers(k);
    for (int i = 0; i < k; i++) {
        cin >> customers[i].x >> customers[i].y >> customers[i].amount;
    }

    blocked.assign(n + 1, vector<bool>(n + 1, false));
    for (int i = 0; i < d; i++) {
        int x, y;
        cin >> x >> y;
        blocked[x][y] = true;
    }

    long long answer = 0;
    for (int i = 0; i < k; i++) {
        answer += (long long)shortest_distance(customers[i].x, customers[i].y) * customers[i].amount;
    }
    cout << answer << '\n';
    return 0;
}

每个客户独立选择最近分店，因为分店没有配送总量限制，客户之间不会互相影响。若对每个客户单独 BFS，会重复遍历同一张网格。

多源 BFS

把所有分店同时加入 BFS 队列，初始距离均为 $0$ 。BFS 第一次到达某个格点时，得到的就是该格点到任意分店的最短距离 dist。之后对每个客户累加 dist[x][y] * amount 即可。

样例中客户的最短距离分别为 $8,5,3$ ，需求量为 $1,3,2$ ，总成本为 $8\times1 + 5\times3 + 3\times2 = 29$ 。其中：

客户 $(1,5)$ 距离 8：来自分店 $(1,1)$ ，需绕过障碍 $(1,2)$ 、 $(2,2)$ ；
客户 $(2,3)$ 距离 5：同样来自分店 $(1,1)$ ；
客户 $(6,7)$ 距离 3：来自分店 $(8,8)$ 。

三个客户分别选择最近的分店配送，因为分店没有配送总量限制，彼此互不影响。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:55
 */
#include <bits/stdc++.h>
using namespace std;

struct Customer {
    int x;
    int y;
    int amount;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k, d;
    cin >> n >> m >> k >> d;

    vector<pair<int, int> > stores(m);
    for (int i = 0; i < m; i++) {
        cin >> stores[i].first >> stores[i].second;
    }

    vector<Customer> customers(k);
    for (int i = 0; i < k; i++) {
        cin >> customers[i].x >> customers[i].y >> customers[i].amount;
    }

    vector<vector<bool> > blocked(n + 1, vector<bool>(n + 1, false));
    for (int i = 0; i < d; i++) {
        int x, y;
        cin >> x >> y;
        blocked[x][y] = true;
    }

    const int INF = 0x3f3f3f3f;
    vector<vector<int> > dist(n + 1, vector<int>(n + 1, INF));
    queue<pair<int, int> > q;
    for (int i = 0; i < m; i++) {
        int x = stores[i].first;
        int y = stores[i].second;
        if (!blocked[x][y] && dist[x][y] == INF) {
            dist[x][y] = 0;
            q.push(make_pair(x, y));
        }
    }

    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};
    while (!q.empty()) {
        pair<int, int> current = q.front();
        q.pop();

        for (int dir = 0; dir < 4; dir++) {
            int nx = current.first + dx[dir];
            int ny = current.second + dy[dir];
            if (nx < 1 || nx > n || ny < 1 || ny > n) {
                continue;
            }
            if (blocked[nx][ny] || dist[nx][ny] != INF) {
                continue;
            }
            dist[nx][ny] = dist[current.first][current.second] + 1;
            q.push(make_pair(nx, ny));
        }
    }

    long long answer = 0;
    for (int i = 0; i < k; i++) {
        answer += (long long)dist[customers[i].x][customers[i].y] * customers[i].amount;
    }

    cout << answer << '\n';
    return 0;
}

复杂度

方格图共有 $n^2$ 个格点，每条道路边只会被 BFS 常数次访问，时间复杂度为 $O(n^2+k)$ ，空间复杂度为 $O(n^2)$ 。

总结

多个起点、边权相同、查询很多时，应把起点一起放入 BFS。一次多源 BFS 共享遍历结果，再用客户需求量作为最后的线性权重。

目录

形式化题目

思路

多源 BFS

代码

复杂度

总结