ABC271E 通る道の長さの最小を求める.最小の長さの合計ではない. 良いpath良いpath とはどういうものかを考えると, \(E\) を先頭から見ていくことで判定できる. そこで \(E\) を基準に考える.また,良いpath 自体は多くなりうるので,Dijikstra などで すべての良いpath を列挙するのは無理そうなので, そういう意味でも \(E\) を基準に考える. Inplace DP (inline DP)\(dp_{i,j} := \) \(E_{[0,j)}\) まで,last が \(i \in V\) minimam cost of good pathsとする.…