1.给定一张 n 个点 m 条边的带权无向联通图，q 次询问，每次询问 ui 到 vi 的最短 路长度。 $n, q ≤ 10^5 , m − n ≤ 20$
题解：
我记得是cf的题
我们只需要先随便搞一颗树
然后对于剩下的$m-n$条边就特殊处理一下
我们把它连$k=2*(m-n)$个点提出来，
然后就有$k^2+m-n$条边（包括原先树上的边构成两点间路径）
对这个跑一遍最短路
然后两点间最短路从a到某个特殊点，再从特殊点到b
本文共 272 字，大约阅读时间需要 1 分钟。
1.给定一张 n 个点 m 条边的带权无向联通图，q 次询问，每次询问 ui 到 vi 的最短 路长度。 $n, q ≤ 10^5 , m − n ≤ 20$
题解：
我记得是cf的题
我们只需要先随便搞一颗树
然后对于剩下的$m-n$条边就特殊处理一下
我们把它连$k=2*(m-n)$个点提出来，
然后就有$k^2+m-n$条边（包括原先树上的边构成两点间路径）
对这个跑一遍最短路
然后两点间最短路从a到某个特殊点，再从特殊点到b
转载于:https://www.cnblogs.com/yinwuxiao/p/10125975.html