- #include <iostream>
- #include <cstring>
- #include <queue>
- using namespace std;
- typedef struct node{
- int row;
- int col;
- int step;
- node(int r,int c,int s){
- row = r;
- col = c;
- step = s;
- }
- }Point;
- int direct[][2] = {-1,0,
- 1,0,
- 0,-1,
- 0,1};
- int buyer[1001][1001];
- int isvisited[1001][1001];
- int n,m,k,d;
- int x,y,c;
- int buyer_cnt;
- queue<Point> q;
- long long ans = 0;
- void bfs()
- {
- Point front(0,0,0) ,v(0,0,0);
- while(!q.empty()){
- front = q.front();
- q.pop();
- for(int i = 0 ; i < 4 ; i++){
- v.row = front.row+direct[i][0];
- v.col = front.col+direct[i][1];
- v.step = front.step+1;
- if(v.row < 1 || v.row > n || v.col < 1 || v.col > n){
- continue;
- }
- if(isvisited[v.row][v.col]){
- continue;
- }
- if(buyer[v.row][v.col] > 0){
- isvisited[v.row][v.col] = 1;
- ans += buyer[v.row][v.col]*v.step;
- buyer_cnt--;
- if(buyer_cnt == 0){
- return;
- }
- }
- isvisited[v.row][v.col] = 1;
- q.push(v);
- }
- }
- }
- int main()
- {
- while(cin>>n>>m>>k>>d){
- memset(buyer,0,sizeof(buyer));
- memset(isvisited,0,sizeof(isvisited));
- buyer_cnt = 0;
- for(int i = 0 ; i < m ; i++){
- cin>>x>>y;
- isvisited[x][y] = 1; //分店搜索时跳过
- q.push(Point(x,y,0));
- }
- for(int i = 0 ; i < k ; i++){
- cin>>x>>y>>c;
- if(buyer[x][y] == 0){
- buyer_cnt++;
- }
- buyer[x][y] += c;
- }
- for(int i = 0 ; i < d ; i++){
- cin>>x>>y;
- isvisited[x][y] = 1;
- }
- bfs();
- cout<<ans<<endl;
- }
- return 0;
- }
复制代码 |