P2934 [USACO09JAN] Safe Travel G 题解

暴力就够了。

建出最短路树，显然删一条边之后的最短路只会经过一条非树边，那考虑枚举一条非树边，假设这条边两端分别为 $u,v$，边权为 $w$，那么显然它只会对 $u,v$ 路径上的点有贡献，同时 $u,v$ 之间的路径长度不会超过 $w$，不然这棵树就不是最短路树了，那么路径上点数也不会超过 $w$，注意到 $w$ 不超过 $1000$，那么直接枚举每个点更新即可，时间复杂度 $O(mV)$，其中 $V$ 是边权上限。