题目思路: 多源路径最短问题
从不同商店出发(商店的数量比较少),不断更新到其他点的最短距离dist[][]
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1010, M = N * N;
typedef pair<int, int> PII;
typedef long long LL;
int n, m, k, d;
int dist[N][N];
queue<PII> q;
bool g[N][N];
struct Consumer{
int x, y, c;
} con[M];
void bfs(){
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
while(q.size()){
PII f = q.front();
q.pop();
for(int i = 0; i < 4; i ++){
int x = f.first + dx[i], y = f.second + dy[i];
if(x > n || x < 1 || y > n || y < 1 || g[x][y]) continue;
if(dist[x][y] > dist[f.first][f.second] + 1){
dist[x][y] = dist[f.first][f.second] + 1;
q.push({x, y});
}
}
}
}
int main()
{
scanf("%d%d%d%d", &n, &m, &k, &d);
memset(dist, 0x3f, sizeof(dist));
while(m --){
int x, y;
scanf("%d%d", &x, &y);
dist[x][y] = 0;
q.push({x, y});
}
for(int i = 0; i < k; i ++){
int x, y, c;
scanf("%d%d%d", &x, &y, &c);
con[i] = {x, y ,c};
}
while (d -- ){
int x, y;
scanf("%d%d", &x, &y);
g[x][y] = true;
}
bfs();
LL res = 0;
for(int i = 0; i < k; i ++){
res += dist[con[i].x][con[i].y] * con[i].c;
}
printf("%lld", res);
return 0;
}