花火大会｜多源不同权的无权最短路问题

第五题 - 花火大会

题目链接跳转：点击跳转

这道题的输出不是故意为难大家，因为输出实在太大了，超出了 CF 限定了 64MB 的限制，因此只能将输出地图改为了输出地图的哈希值（对于没有学过哈希的同学来说，输出答案也是一个比较困难的事情）。

本道题的难度其实不大，就是一个多源不同权的无权最短路问题。但由于数据量比较大，使用普通的优先队列维护会超时（别问我是怎么知道的，我一开始就用了优先队列，然后在 #13 测试点就 TLE 了），因此我们需要考虑如何找到一个 workaround 来替换优先队列。

注意到我们只需要另外再使用一个 while，在每次获取头节点的时候判断某一个烟花是否刚好在该时间点燃放，如果烟花正好燃放，我们就把这个烟花的坐标加入到队列之中。

while(arr[cnt].z <= t.z && cnt <= k){
    vis[arr[cnt].x][arr[cnt].y] = 1;
    que.push(arr[cnt]); cnt ++;
}

由于每一个烟花每一个单位时间只会影响附近的一个格子，说明在放入烟花的时候队列中队头和队尾的权重是相同的，这样就保证队列内的元素权重一定是单调递增的。这这种情况下，这道题就转换成了使用 BFS 来求多源无权最短路的条件。

本题的 AC 代码如下：

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int MOD = 998244353;

int n, m, k, cnt = 2;
struct node{
    int x, y, z;
} arr[1005]; 
queue<node> que;
int dis[5005][5005];
int vis[5005][5005];
int dx[] = {0, 1, -1, 0};
int dy[] = {1, 0, 0, -1};

bool cmp(node a, node b){
    return a.z < b.z;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> m >> k;
    for (int i=1, x, y, z; i<=k; i++)
        cin >> arr[i].x >> arr[i].y >> arr[i].z;

    sort(arr+1, arr+1+k, cmp);
    que.push(arr[1]);
    vis[arr[1].x][arr[1].y] = 1;

    while(!que.empty()){
        node t = que.front();
        que.pop();
        if (dis[t.x][t.y]) continue;
        dis[t.x][t.y] = t.z;
        while(arr[cnt].z <= t.z && cnt <= k){
            vis[arr[cnt].x][arr[cnt].y] = 1;
            que.push(arr[cnt]); cnt ++;
        }
        for (int i=0; i<4; i++){
            int cx = dx[i] + t.x;
            int cy = dy[i] + t.y;
            if (cx < 1 || cy < 1 || cx > n || cy > m) continue;
            if (dis[cx][cy]) continue; 
            if (vis[cx][cy]) continue;
            vis[cx][cy] = 1;
            que.push((node){cx, cy, t.z+1});
        }
    }
    
    long long ans = 0, p = 1;
    for (int i=1; i<=m; i++) 
        p = (p * 233) % MOD;
    for (int i=1; i<=n; i++){
        for (int j=1; j<=m; j++){
            p = (p * 233) % MOD;
            ans = (ans + (dis[i][j] * p) % MOD) % MOD;
        }
    }

    cout << ans << endl;
    return 0;
}