题目解析
本题若只有一处放烟花的地方，那么则为「单源无权最短路问题」。
当有多处放烟花的地方且放烟花的时间相同，则为「多源无权最短路问题」。
以上两个问题都可以使用 BFSBFSBFS 解决。但本题需要解决的是一个「多源不同权的无权最短路问题」。
容易想到的一个策略是使用「优先队列」替换「队列」来实现 BFSBFSBFS。但此种方法的复杂度为 O(NMlogNM)\mathrm{O}(NM\log{NM})O(NMlogNM) 在本题时间复杂度比较大的情况下无法通过本题。
假设队列中的点是按照最短路的大小从小到大排好序的，例如以下：
[1,2,2,2,3,3,3,4,5][1, 2, 2, 2, 3, 3, 3, 4, 5][1,2,2,2,3,3,3,4,5]
第一个点的最短路为 111，当其出队的时候，扩展的到的点的最短路为 222。
我们需要将其放在一个合适的位置，使得每个点第一次出队的时候，一定是未确定最短路的点中，最短路最小的点（DijkstraDijkstraDijkstra 算法的思想）。
那么我们不妨将这些点按照最短路大小进行分组：
[[1],[2,2,2],[3,3,3],[4],[5]][[1], [2, 2, 2], [3, 3, 3], [4], [5]][[1],[2,2,2],[3,3,3],[4],[5]]
我们只要能够从小到大依次遍历这些组，并将扩展出的点放入对应的「组」中即可。
这里可以采用「计数排序」的思想，对于最短路不同的点，使用一个独立的「队列」保存。
由于本题为「格点无权图」，令最短路最小的点的权值为 deltadeltadelta, 那么，最短路大的点的最短路的值不超过 delta+N+M−2delta + N + M - 2delta+N+M−2，所以我们只需要开一个大小为 N+MN + MN+M 的「队列数组」即可。
然后依次访问所有的队列，并将当前队列中拓展出的点，放入下一个队列中即可。
那么由于每个点只会「出队/入队」常数次，且一共访问 N+M−2N + M - 2N+M−2 个队列，总的时间复杂度为 O(N+M+N×M)\mathrm{O}(N + M + N \times M)O(N+M+N×M)。
AC代码
