官方题解｜花火大会

题目解析

本题若只有一处放烟花的地方，那么则为「单源无权最短路问题」。
当有多处放烟花的地方且放烟花的时间相同，则为「多源无权最短路问题」。

以上两个问题都可以使用 $BFS$ 解决。但本题需要解决的是一个「多源不同权的无权最短路问题」。

容易想到的一个策略是使用「优先队列」替换「队列」来实现 $BFS$。但此种方法的复杂度为 $\mathrm{O}(NM\log{NM})$ 在本题时间复杂度比较大的情况下无法通过本题。

假设队列中的点是按照最短路的大小从小到大排好序的，例如以下：

$[1, 2, 2, 2, 3, 3, 3, 4, 5]$

第一个点的最短路为 $1$，当其出队的时候，扩展的到的点的最短路为 $2$。
我们需要将其放在一个合适的位置，使得每个点第一次出队的时候，一定是未确定最短路的点中，最短路最小的点（$Dijkstra$ 算法的思想）。

那么我们不妨将这些点按照最短路大小进行分组：

$[[1], [2, 2, 2], [3, 3, 3], [4], [5]]$

我们只要能够从小到大依次遍历这些组，并将扩展出的点放入对应的「组」中即可。

这里可以采用「计数排序」的思想，对于最短路不同的点，使用一个独立的「队列」保存。

由于本题为「格点无权图」，令最短路最小的点的权值为 $delta$, 那么，最短路大的点的最短路的值不超过 $delta + N + M - 2$，所以我们只需要开一个大小为 $N + M$ 的「队列数组」即可。

然后依次访问所有的队列，并将当前队列中拓展出的点，放入下一个队列中即可。

那么由于每个点只会「出队/入队」常数次，且一共访问 $N + M - 2$ 个队列，总的时间复杂度为 $\mathrm{O}(N + M + N \times M)$。

AC代码

#include <bits/stdc++.h>

template<class T>
using Vec = std::vector<T>;
template<class T>
using VVec = std::vector<Vec<T>>;

constexpr int dirs[][2] {0, 1, 1, 0, 0, -1, -1, 0};
constexpr int MOD = 998244353;
constexpr int BASE = 233;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int n, m, k;
    std::cin >> n >> m >> k;
    Vec<std::tuple<int, int, int>> a(k);
    int delta = 1e9;
    for (auto &[x, y, z] : a) {
        std::cin >> x >> y >> z;
        delta = std::min(delta, z);
    }
    Vec<std::queue<std::pair<int, int>>> q(n + m);
    for (auto &[x, y, z] : a)
        if (z - delta < n + m)
            q[z - delta].emplace(x - 1, y - 1);
    VVec<int> dist(n, Vec<int>(m));
    for (int i = 0; i < n + m - 1; ++i)
        while (!q[i].empty()) {
            auto [x, y] = q[i].front(); q[i].pop();
            if (dist[x][y]) continue;
            dist[x][y] = i + delta;
            for (auto &[dx, dy] : dirs) {
                int nx = x + dx, ny = y + dy;
                if (nx < 0 or nx >= n or ny < 0 or ny >= m) continue;
                if (dist[nx][ny]) continue;
                q[i + 1].emplace(nx, ny);
            }
        }
    int res = 0, base = BASE;
    for (int i = 0; i < m; ++i)
        base = (1LL * base * BASE) % MOD;
    for (auto &row : dist) for (auto &x : row) {
        res = (res + 1LL * x * base) % MOD;
        base = 1LL * base * BASE % MOD;
    }
    std::cout << res << '\n';
    return 0;
}