考虑对两个通讯网络进行dij最短路，设\(d[1][i]\)为\(w_1 \to i\)的最短路，\(d[2][i]\)为\(w_2 \to i\)的最短路，那么对于两个基站\((u,v)\)对答案的贡献就为\(\min(d[1][u] + d[1][v],d[2][u] + d[2][v])\)。
于是很简单地，我们可以得到一个\(\mathcal{O}(k ^ 2 + DIJ)\)做法，DIJ为dij的时间复杂度。
考虑优化，我们考虑枚举\(u\)，有多少点是通过\(w_1\)过来的，有多少是通过\(w_2\)过来的。设\(w_1\)过来的有\(f_i\)个，总和为\(g_i\)，那么对答案的贡献为\(g_i + f_i \times g_i\)，\(w_2\)类似。
从\((u,v)w_1\)过来，当且仅当\(d[1][u] + d[1][v] \le d[2][u] + d[2][v]\)，得\(d[1][u] - d[2][u] \le d[2][v] - d[1][v]\)，树状数组维护既珂。
原文：https://www.cnblogs.com/luyiming123blog/p/14161317.html