简单的多源bfs,没啥好说的,主要是写代码的技巧
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
const int N=1010;
int need[N*N];
vector<PII> shop,guke;
int dist[N][N];
bool st[N][N];
int n,m,k,d;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
void bfs(){
memset(dist,0x3f,sizeof dist);
queue<PII> q;
for(auto t:shop){
int x=t.first,y=t.second;
q.push({x,y});
dist[x][y]=0;
}
while(q.size()){
auto t=q.front();q.pop();
int x=t.first,y=t.second;
if(st[x][y]) continue;
st[x][y]=true;
for(int i=0;i<4;i++){
int xx=x+dx[i],yy=y+dy[i];
if(xx<1||xx>n||yy<1||yy>n||st[xx][yy]) continue;
if(dist[xx][yy]>dist[x][y]+1){
dist[xx][yy]=dist[x][y]+1;
q.push({xx,yy});
}
}
}
}
int main(){
n=read(),m=read(),k=read(),d=read();
for(int i=0;i<m;i++){
int x=read(),y=read();
shop.push_back({x,y});
}
for(int i=0;i<k;i++){
int x=read(),y=read(),ne=read();
need[i]=ne;
guke.push_back({x,y});
}
for(int i=0;i<d;i++){
int a=read(),b=read();
st[a][b]=true;
}
bfs();
ll ans=0;
for(int i=0;i<k;i++){
auto t=guke[i];
int x=t.first,y=t.second;
ans+=1ll*need[i]*dist[x][y];
}
cout<<ans;
return 0;
}