题解：SP215 PANIC - Panic in the Plazas

Emily1234 · 2025-11-22 15:03:42 · 题解

题解：SP215 PANIC - Panic in the Plazas

首先，求关，代码吗......，成功WA了，姐把思路说一下吧

检察官大大让我过吧，这个题，就我一篇题解还不过那就.......

问题分析

本题的核心是计算每个广场的恐慌到达时间，找到最大恐慌到达时间对应的所有广场并按升序输出。恐慌传播可抽象为带权有向图的多源最短路径问题：炸弹广场为源点（初始恐慌时间为 0），街道的单向通行时间为边权，恐慌到达时间即为源点到该节点的最短路径长度。

关键规则解读：

• 炸弹广场的恐慌到达时间为 0。
• 恐慌沿街道传播的时间为街道的单向通行时间。

• 若街道双向同时有恐慌传播（相向而行），会导致踩踏，但最短路径算法会自然规避这种冲突（因为最短路径会选择最优的传播方向，冲突路径不会成为最短路径）。

算法选择

1. 堆优化的 Dijkstra 算法：适用于正权边的最短路径计算，本题中街道通行时间均为正，符合算法要求
2. 邻接表存储图：广场数量n \le 50000，街道数量m\le 250000，邻接表能高效存储图结构，避免邻接矩阵的空间浪费。
3. 多源初始化：将所有炸弹广场的初始距离设为 0，加入优先队列，实现多源最短路径计算。