308H

考虑枚举唯一一个度数为 $3$ 的点 $u$，即既在环上又与非环上一点相连的那个点。 接下来考虑先处理环，那可以先把 $u$ 从图上删掉，环的最短距离便是与 $u$ 有连边的 $2$ 个点在图上最短路长度加上 $2$ 个点与 $u$ 连边的长度，即 $\min\{w_{u, i} + w_{u, j ......