货物运输 (good)

 1 #include <stack>
 2 #include <queue>
 3 #include <cmath>
 4 #include <vector>
 5 #include <cstdio>
 6 #include <cstring>
 7 #include <iostream>
 8 #include <algorithm>
 9 #define fi first
10 #define se second
11 #define IL inline
12 #define RG register
13 #define MP(a,b) make_pair(a,b)
14 #define PI acos(-1)
15 #define Mod 998244353
16 using namespace std;
17 typedef long long LL;
18 typedef unsigned long long ULL;
19 typedef double DB;
20 typedef pair<int, int> PR;
21 const int N = 1009;
22 const int M = 126750;
23 int gx[] = {0, 0, 1, -1};
24 int gy[] = {1, -1, 0, 0};
25 int n, m, k, d;
26 LL f[N][N], w[N*N], ans;
27 bool v[N][N];
28 vector<PR> shop, station;
29 queue<PR> q;
30 IL int read()
31 {
32     int num = 0; bool flag = 0; char c;
33     while((c=getchar())==‘ ‘ || c==‘\n‘ || c==‘\r‘);
34     if(c == ‘-‘) flag = 1; else num = c - ‘0‘;
35     while(isdigit(c=getchar()))
36         num = num * 10 + c - ‘0‘;
37     return flag ? -num : num;
38 }
39 IL int mabs(int x)
40 {
41     return x < 0 ? -x : x;
42 }
43 
44 int main(void)
45 {
46     n = read(); m = read(); k = read(); d = read();
47     memset(f, 0x3f, sizeof(f));
48     shop.resize(m);
49     station.resize(k);
50     for(int i = 0; i < m; i++)
51     {
52         shop[i].fi = read();
53         shop[i].se = read();
54         f[shop[i].fi][shop[i].se] = 0;
55         q.push(shop[i]);
56     }
57     for(int i = 0; i < k; i++)
58     {
59         station[i].fi = read();
60         station[i].se = read();
61         w[i] = read();
62     }
63     for(int i = 0; i < d; i++)
64     {
65         int x = read(), y = read();
66         v[x][y] = 1;
67     }
68     while(!q.empty())
69     {
70         PR now = q.front();
71         q.pop();
72         for(int i = 0; i < 4; i++)
73         {
74             int x = now.fi + gx[i];
75             int y = now.se + gy[i];
76             if(x < 1 || x > n || y < 1 || y > n) continue;
77             if(v[x][y]) continue;
78             if(f[now.fi][now.se]+1>=f[x][y]) continue;
79             f[x][y] = f[now.fi][now.se] + 1LL;
80             q.push(MP(x, y));
81         }
82     }
83     for(int i = 0; i < k; i++)
84         ans += w[i] * f[station[i].fi][station[i].se];
85     printf("%lld\n", ans);
86     return 0;
87 }