【GJOI 2023.10.6 T2】 亿只只因的回家路

亿只只因的回家路

题意：给出一个 \(n\) 点 \(m\) 边的无向图，每条边有长度 \(v_i\) ， 有 \(k\) 只小鸡，第 \(i\) 只小鸡在 \(id_i\) 号节点，鸡妈妈在 \(1\) 号点，现鸡妈妈要接所有的小鸡，小鸡与鸡妈妈的速度为 \(1\) ，问最短多久鸡妈妈才能接到所有的小鸡 ，\(n \le 10^5,k \le 2 \times 10^5\)。
由于他们的速度都是 \(1\) ，所以可以看到他们都会集中到一个汇合点。
转化成他们到一个点的最短时间是多少。
由于这个点可能在边上，所以我们需要分类讨论。
找出这堆鸡到每个点的最短距离，时间复杂度 \(O(knlogn)\) 。
枚举点