P8906[USACO22DEC]BreakdownP题解显然的套路是删边转化为加边。考虑到维护整条路径不好维护，于是考虑转化维护\(f_{i,k},g_{i,k}\)分别表示\(1,n\)到\(i\)走了\(k\)步时的最短路。那么此时\(k\le4\)。我们先考虑\(f\)的转移，\(g\)的转移是等价的。那么对于\((