题目描述

栋栋最近开了一家餐饮连锁店，提供外卖服务。

随着连锁店越来越多，怎么合理的给客户送餐成为了一个急需解决的问题。

栋栋的连锁店所在的区域可以看成是一个 n×n 的方格图（如下图所示），方格的格点上的位置上可能包含栋栋的分店（绿色标注）或者客户（蓝色标注），有一些格点是不能经过的（红色标注）。

方格图中的线表示可以行走的道路，相邻两个格点的距离为 1。

栋栋要送餐必须走可以行走的道路，而且不能经过红色标注的点。

送餐的主要成本体现在路上所花的时间，每一份餐每走一个单位的距离需要花费 1 块钱。

每个客户的需求都可以由栋栋的任意分店配送，每个分店没有配送总量的限制。

现在你得到了栋栋的客户的需求，请问在最优的送餐方式下，送这些餐需要花费多大的成本。

输入格式
输入的第一行包含四个整数 n,m,k,d，分别表示方格图的大小、栋栋的分店数量、客户的数量，以及不能经过的点的数量。

接下来 m 行，每行两个整数 xi,yi，表示栋栋的一个分店在方格图中的横坐标和纵坐标。

接下来 k 行，每行三个整数 xi,yi,ci，分别表示每个客户在方格图中的横坐标、纵坐标和订餐的量。（注意，可能有多个客户在方格图中的同一个位置）

接下来 d 行，每行两个整数，分别表示每个不能经过的点的横坐标和纵坐标。

输出格式
输出一个整数，表示最优送餐方式下所需要花费的成本。

数据范围
前 30% 的评测用例满足：1≤n≤20。
前 60% 的评测用例满足：1≤n≤100。
所有评测用例都满足：1≤n≤1000,1≤m,k,d≤n2。
可能有多个客户在同一个格点上。
每个客户的订餐量不超过 1000，每个客户所需要的餐都能被送到。

样例

输入样例：
10 2 3 3
1 1
8 8
1 5 1
2 3 3
6 7 2
1 2
2 2
6 8
输出样例：
29

BFS

$O(m * n^2)$

多源bfs,对每个店铺同时进行bfs,每个店铺都用不同的标号表示,采用类似染色法的思路,当遇到一个客户,就根据
节点颜色确定离其最近的店铺,时间复杂度O(m * n^2),只用进行一次bfs即可

C++ 代码

#include <iostream>
#include <cstring>
#include <cmath>
#include <queue>

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int N = 1010, M = 10000010;

int g[N][N];
bool vis[N][N];
queue<PII> q;

int id[M], width[M];    //分别表示店铺对应的id和对应店铺扩展的宽度
int store[M][2];    //记录店铺坐标
int n, m, k, d, tot;
LL ans;

const int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

void bfs(){
    int cnt = 0;
    while(!q.empty()){
        int s = q.size();
        for(int i = 0; i < s; i++){
            auto t = q.front(); q.pop();
            int x = t.first, y = t.second;
            int idx = x * n + y;
            int tid = id[idx];  //找到当前点所属的店铺id

            if(g[x][y] > 0){    //遇到客户
                ans += (LL)width[tid] * g[x][y];
                cnt++;
                if(cnt == k) return;    //剪枝
                }

            for(int j = 0; j < 4; j++){
                int dx = x + dir[j][0], dy = y + dir[j][1];
                if(dx > 0 && dx <= n && dy > 0 && dy <= n && !vis[dx][dy] && g[dx][dy] != -1){
                    vis[dx][dy] = true;
                    id[dx * n + dy] = id[x * n + y];
                    q.push({dx, dy});
                    }
                }
            }
        //每过一轮宽度增加1
        for(int i = 0; i < m; i++){
            int idx = store[i][0] * n + store[i][1];
            int tid = id[idx];
            width[tid]++;
            }
        }
}


int main(){
    scanf("%d %d %d %d", &n, &m, &k, &d);
    int x, y, c;
    for(int i = 0; i < m; i++){
        scanf("%d %d", &x, &y);
        q.push({x, y}); //店铺入队
        store[i][0] = x, store[i][1] = y;
        vis[x][y] = true;
        int idx = x * n + y;    //二维化一维
        id[idx] = ++tot;
        }

    for(int i = 0; i < k; i++){
        scanf("%d %d %d", &x, &y, &c);
        g[x][y] += c;    // > 0 表示客户
        }

    for(int i = 0; i < d; i++){
        scanf("%d %d", &x, &y);
        g[x][y] = -1;   //表示障碍物
        }

    bfs();

    printf("%lld\n", ans);

    return 0;
}

BFS(优化)

$O(n^2)$

观察可知上面的width数组其实是不需要的，用一个变量表示即可，因为每个点的范围都是同时增长的,因此id数组其实也是不需要的，我们可以进一步优化时间和空间

C++ 代码

#include <iostream>
#include <cstring>
#include <cmath>
#include <queue>

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int N = 1010;

int g[N][N];
bool vis[N][N];
queue<PII> q;

int n, m, k, d, tot;
LL ans;

const int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

void bfs(){
    int cnt = 0;
    LL w = 0;
    while(!q.empty()){
        int s = q.size();
        for(int i = 0; i < s; i++){
            auto t = q.front(); q.pop();
            int x = t.first, y = t.second;

            if(g[x][y] > 0){    
                ans += w * g[x][y];
                cnt++;
                if(cnt == k) return;    
                }

            for(int j = 0; j < 4; j++){
                int dx = x + dir[j][0], dy = y + dir[j][1];
                if(dx > 0 && dx <= n && dy > 0 && dy <= n && !vis[dx][dy] && g[dx][dy] != -1){
                    vis[dx][dy] = true;
                    q.push({dx, dy});
                    }
                }
            }

        w++;
        }
}


int main(){
    scanf("%d %d %d %d", &n, &m, &k, &d);
    int x, y, c;
    for(int i = 0; i < m; i++){
        scanf("%d %d", &x, &y);
        q.push({x, y}); 
        vis[x][y] = true;
        }

    for(int i = 0; i < k; i++){
        scanf("%d %d %d", &x, &y, &c);
        g[x][y] += c;   
        }

    for(int i = 0; i < d; i++){
        scanf("%d %d", &x, &y);
        g[x][y] = -1;   
        }

    bfs();

    printf("%lld\n", ans);

    return 0;
}