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
| #include <bits/stdc++.h> #include <unordered_map> using namespace std;
typedef long long ll; const int N= 1000 + 10; const int NOT = -1;
int ma[N][N]; ll dis[N][N];
struct state{ int x_, y_; ll step_; };
const int dir[4][2] = { {-1,0},{0,-1}, {1,0},{0,1} };
inline bool isvalid(int x, int y, int n){ return (x<n)&&(y<n)&&(x>=0)&&(y>=0)&&(dis[x][y] == LONG_MAX)&&ma[x][y]!=NOT; }
int main(){ int n,m,k,d; scanf("%d %d %d %d",&n,&m,&k,&d); memset(ma,0,sizeof ma); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ dis[i][j] = LONG_MAX; } } queue<state>q; for(int i=0;i<m;i++){ int x,y; scanf("%d %d",&x, &y); dis[x-1][y-1] = 0; q.push(state{x-1, y-1, 0}); } unordered_map<int,ll>hash; for(int i=0;i<k;i++){ int x,y,c; scanf("%d %d %d",&x, &y,&c); hash[x-1+(y-1)*n] +=c; } for(int i=0;i<d;i++){ int x,y; scanf("%d %d",&x, &y); ma[x-1][y-1] = NOT; } while(q.size()){ state cur = q.front();q.pop(); for(int i=0;i<4;i++){ int x = cur.x_ + dir[i][0], y = cur.y_ + dir[i][1]; if (isvalid(x, y,n)){ dis[x][y] = cur.step_+1; q.push(state{x, y, cur.step_+1}); } } } ll ans =0; for(auto t:hash){ int pos = t.first;ll cost = t.second; int x = pos%n, y = pos/n; ans += dis[x][y] * cost; } cout<<ans<<endl; return 0; }
|