如标签所说,多源BFS
如果没头绪的小伙伴可以瞅一下 这个博客

这里再大概说下怎么回事:
我们可以假设一个总店,总店到所有分店距离为0,因此我们只要从总店开始BFS就行(变成单源),
然后对于每一个分店,我们总会比其他分店更快地遍历到离他更近的客户,
因此我们对每一个客户只要遍历一次

时间复杂度:
O(n²)

#include <iostream>
#include <cstring>
#include <queue>
#include <map>
using namespace std;
int dis[1005][1005];
typedef long long ll;
void ini() {
    memset(dis,0x3f,sizeof(dis));
    for(int i=0; i<=1000; i++)
        dis[0][i] = dis[i][0] = -1;
}
bool ok(int x,int y,int n) {
    return (x >= 1 && x <= n && y >= 1 && y <= n);
}
struct point {
    int x,y;
    int cnt;
    point(int x = 0,int y = 0,int cnt = 0):x(x),y(y),cnt(cnt) {}
};
int fx[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
int main() {
    ini();

    int n,m,k,d;
    scanf("%d %d %d %d",&n,&m,&k,&d);

    point store[m],peo[k];
    for(int i=0; i<m; i++) //分店
        scanf("%d %d",&store[i].x,&store[i].y);

    for(int i=0; i<k; i++)
        scanf("%d %d %d",&peo[i].x,&peo[i].y,&peo[i].cnt);

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

    queue<point> que;
    for(int i=0; i<m; i++) {
        int x,y;
        x = store[i].x,y = store[i].y;

        que.push({x,y,0});
    }

    const int inf = dis[store[0].x][store[0].y];

    while(!que.empty()) {
        point t = que.front();
        que.pop();
        int x = t.x,y = t.y;

        for(int j=0; j<4; j++) {
            int nx = x + fx[j][0],ny = y + fx[j][1];
            if(!ok(nx,ny,n) || dis[nx][ny] == -1 || dis[nx][ny] != inf)continue;

            que.push({nx,ny,t.cnt+1});
            dis[nx][ny] = t.cnt+1;
        }
    }
    ll ans = 0;
    for(int i=0; i<k; i++) {
        int x,y;
        x = peo[i].x,y = peo[i].y;
        ans += 1ll*dis[x][y]*peo[i].cnt;
    }
    printf("%lld",ans);
    return 0;
}