P3547 [POI2013] CEN-Price List

很不错的图论题。

考虑对 \(a,2a,b\) 大小进行讨论。

1. \(2a \le b\)，这种情况是简单的，根本不会走 \(b\) 边，直接 bfs 即可，此时答案为 \(d*a\)。

2. \(a \le b < 2a\)，这种情况下能走两条 \(a\) 边就会用 \(b\) 边替换掉，同时不用担心三元环的情况（因为三元环会出现三个点最短路都是 \(1\)，但是从 \(u \to v \to w\) 的 \(2a\) 被替换成 \(b\)），此时答案为 \(\frac{d}{2}*b+[d\bmod2]*b\)。

3. \(b < a\)，此时可能出现为了多走 \(b\) 而少走 \(a\) 的情况，此时答案为 \(\min(D*b,\frac{d}{2}*b+[d\bmod2]*b)\)，注意这里的 \(D\) 指的是每次走两步的最短路。

由于求最小值，对上面几种情况取 \(\min\) 即可。

除了 \(d'\) 其他都是平凡的。

暴力考虑每次扩展两条边，复杂度为 \(m^2\)，注意对于三个点 \(u,v,w\) 来说，若出现 \(u \to v \to w\) 的扩展，则说明 \(D_{w} > D_{u}\)，也就不可能出现 \(w \to u\) 的扩展，同理若 \(u,w\) 同时能扩展到的点也不会以 \(w\) 扩展，故可删除 \((v,w)\) 这条边。

再次思考下复杂度，此时的三元环会被扩展最多三边，而其他边扩展一次会被删除，总复杂度为三元环个数，复杂度为 \(O(m \sqrt m)\)。