本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-10-15 17:32:14

[ABC375G] Road Blocked 2

题目考察：dijkstra，哈希。
题目简述： 在一个图 $G$ 中，有 $n$ 个点，$m$ 条边（表示为 $u_i,v_i,w_i$），$m$ 个询问，第 $i$ 次询问去掉第 $i$ 条边后从 $1$ 到 $n$ 是否不连通或最短路的值改变（询问是独立的）。
数据范围：

• $2\le n\le 2\times 10^5$
• $1\le m\le 2\times 10^5$
• $1\le u_i<v_i\le n$
• $1\le w_i\le 10^9$
• $G$ 中无重边，点 $1$ 到点 $n$ 联通。

满足该条件，当且仅当所有的最短路都经过这条边，然后需要满足两个条件：

• 首先最短路要经过这条边。
• 然后经过这条边的最短路数等于总的最短路数。

那么我们继续思考（设 $dis_{u,v}$ 为 $u$ 到 $v$ 的最短路，$cnt_{u,v}$ 为从 $u$ 到 $v$ 的最短路数）：

• 最短路经过第 $i$ 边说明 $dis_{1,u_i}+w_i+dis_{v_i,n}=dis_{1,n}$。
• 经过这条边的最短路数等于总的最短路数说明 $cnt_{1,u_i}\times cnt_{v_i,n}=cnt_{1,n}$。

这两个值是可以分别从 $1$ 和 $n$ 分别跑 dijkstra 用 $\Theta((n+m)\log n)$ 求出来，但是 $cnt_{1,n}$ 的值非常大，所以我们要用哈希。

时间复杂度为 $\Theta((n+m)\log n)$。

代码