如果读数据要读$10^5$以上的次数,那建议用scanf或者优化cin
这个题m,k,d最大可以是1e6
优化cin
// 多源bfs模板题
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e3 + 7;
typedef pair<int, int> PII;
typedef long long LL;
int n, m, k, d;
int x, y, c;
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
LL numbers[N][N];
int dist[N][N];
char g[N][N];
int main() {
std::ios::sync_with_stdio(false); // 必须关闭stdin同步,不然cin会超时
// 方格图的大小、栋栋的分店数量、客户的数量,以及不能经过的点的数量
cin >> n >> m >> k >> d;
queue<PII> q;
memset(dist, 0x3f, sizeof dist);
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++) g[i][j] = 'o';
for (int i = 1; i <= m; i ++) {
cin >> x >> y;
g[x][y] = '*'; // 分店
dist[x][y] = 0;
q.push({x, y}); // 多源bfs 起点
}
for (int i = 1; i <= k; i ++) {
cin >> x >> y >> c;
g[x][y] = '.'; // 客户
numbers[x][y] += c;
}
for (int i = 1; i <= d; i ++) {
cin >> x >> y;
g[x][y] = '#'; // 障碍物
}
// 计算dist距离
while (q.size()) {
auto t = q.front();
q.pop();
int x = t.first, y = t.second;
for (int d = 0; d < 4; d ++) {
int a = x + dx[d], b = y + dy[d];
if (1 <= a && a <= n && 1 <= b && b <= n && g[a][b] != '#') {
if (dist[a][b] == 0x3f3f3f3f) {
dist[a][b] = dist[x][y] + 1;
q.push({a, b});
}
}
}
}
LL res = 0;
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= n; j ++) {
if (g[i][j] == '.') {
res += (numbers[i][j] * 1ll * dist[i][j]);
}
}
}
cout << res << endl;
return 0;
}
scanf
// 多源bfs模板题
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e3 + 7;
typedef pair<int, int> PII;
typedef long long LL;
int n, m, k, d;
int x, y, c;
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
LL numbers[N][N];
int dist[N][N];
char g[N][N];
struct Target
{
int x, y, c;
}tg[N * N];
int main() {
// 方格图的大小、栋栋的分店数量、客户的数量,以及不能经过的点的数量
scanf("%d%d%d%d", &n, &m, &k, &d);
// cin >> n >> m >> k >> d;
queue<PII> q;
memset(dist, 0x3f, sizeof dist);
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++) g[i][j] = 'o';
for (int i = 1; i <= m; i ++) {
// scanf("%d%d", &x, &y);
cin >> x >> y;
g[x][y] = '*'; // 分店
dist[x][y] = 0;
q.push({x, y}); // 多源bfs 起点
}
for (int i = 1; i <= k; i ++) {
scanf("%d%d%d", &tg[i].x, &tg[i].y, &tg[i].c);
// cin >> x >> y >> c;
// tg[i] = {x, y, c};
}
for (int i = 1; i <= d; i ++) {
scanf("%d%d", &x, &y);
// cin >> x >> y;
g[x][y] = '#'; // 障碍物
}
// 计算dist距离
while (q.size()) {
auto t = q.front();
q.pop();
int x = t.first, y = t.second;
for (int d = 0; d < 4; d ++) {
int a = x + dx[d], b = y + dy[d];
if (1 <= a && a <= n && 1 <= b && b <= n && g[a][b] != '#') {
if (dist[a][b] == 0x3f3f3f3f) {
dist[a][b] = dist[x][y] + 1;
q.push({a, b});
}
}
}
}
LL res = 0;
for (int i = 1; i <= k; i ++) {
res += dist[tg[i].x][tg[i].y] * tg[i].c;
}
cout << res << endl;
return 0;
}