题解：SP215 PANIC - Panic in the Plazas

题解：SP215 PANIC - Panic in the Plazas

问题分析

关键规则解读：

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

算法选择

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