[ABC375G] Road Blocked 2 讲解

zrl123456 · 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
• --- 满足该条件，当且仅当所有的最短路都经过这条边，然后需要满足两个条件：
• 首先最短路要经过这条边。
• 然后经过这条边的最短路数等于总的最短路数。

那么我们继续思考（设 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)。

代码