题意

我们有一个连通无向图，需要选择参数 $X$，然后：

1. 修建地下通道：所有与广场 $1$ 距离 $\leq X$ 的广场之间互相连通

   • 花费：$C \times X$

2. 修补道路：对于每条道路，如果它的两个端点都距离广场 $1$ > $X$，则需要修补

   • 花费：道路的长度 $D_i$

目标：最小化总花费（地下通道花费 + 道路修补花费）

关键观察

1. 最优 $X$ 的候选值

重要性质：最优的 $X$ 一定是某个广场到广场 $1$ 的距离 $dist[i]$。

证明：如果 $X$ 在区间 $(dist[k], dist[k+1])$ 内：

• 将 $X$ 减小到 $dist[k]$：地下通道花费减少，需要修补的道路可能减少或不变
• 总花费不会增加，可能减少

因此只需考虑 $X = dist[i]$ 和 $X = 0$。

2. 道路修补条件

对于边 $(u, v, d)$，需要修补 当且仅当：

因为如果至少一个端点距离 $\leq X$，那么该端点通过地下通道与广场 $1$ 连通，另一端点也可以通过地下通道到达，不需要修补这条道路。

算法思路

步骤 1：计算最短路径

从广场 $1$ 出发，使用 Dijkstra 算法计算到所有广场的最短距离 $dist[1..N]$。

步骤 2：预处理边信息

对于每条边 $i = (A_i, B_i, D_i)$，计算：

将边按 $maxDist$ 排序。

步骤 3：计算前缀和

计算排序后边长的前缀和数组 $prefixSum$，用于快速计算 $maxDist > X$ 的所有边的总长度。

步骤 4：枚举候选 $X$

考虑所有 $dist[i]$ 作为候选 $X$，对于每个 $X$：

1. 地下通道花费：$C \times X$
2. 道路修补花费：所有 $maxDist > X$ 的边的 $D_i$ 之和
3. 总花费：两者相加

使用二分查找快速定位 $maxDist > X$ 的边。

步骤 5：取最小值

所有候选 $X$ 对应的总花费的最小值。

复杂度分析

• Dijkstra：$O(M \log N)$
• 排序边：$O(M \log M)$
• 枚举候选值：$O(N \log M)$（二分查找）
• 总复杂度：$O(M \log N)$，适合题目数据范围

样例验证

样例 1

输入：
5 5 2
2 3 1
3 1 2
2 4 3
1 2 4
2 5 5

计算过程：
1. 计算dist: dist[1]=0, dist[2]=2, dist[3]=2, dist[4]=5, dist[5]=7
2. 边信息：
   (1,2,4): maxDist=2
   (1,3,2): maxDist=2  
   (2,3,1): maxDist=2
   (2,4,3): maxDist=5
   (2,5,5): maxDist=7
3. 排序边：按maxDist=[2,2,2,5,7]
4. 前缀和：[0,4,8,11,16,21]
5. 枚举候选X：
   - X=0: 花费=0+21=21
   - X=2: 花费=4+(21-8)=17
   - X=5: 花费=10+(21-16)=15
   - X=7: 花费=14+0=14
最小值为14

总结

这道题的关键在于：

1. 识别最优解结构：$X$ 一定是某个 $dist[i]$
2. 转化修补条件：$\max(dist[u], dist[v]) > X$
3. 使用前缀和优化：快速计算道路修补花费