POI 2013
Price List
设只包含 \(a\) 边的图是 \(G=(V,E)\)。
注意到答案只有三种可能：只走 \(a\) 边，走恰好一条 \(a\) 边和若干条 \(b\) 边，以及只走 \(b\) 边。
对于前两种，直接 BFS 即可求出。对于第三种，因为只需要考虑 \(b\) 边，所以仍然可以 BFS。设当前 BFS 到点 \(u\)，那么其实就是要枚举 \((u,v)\in E,(v,w)\in E,(u,w)\not\in E\)，且 \(w\) 未被 BFS 到过，并令 \(\mathrm{dis}_w=\mathrm{dis}_u+b\)。
那么可以将枚举的范围改成 \((u,v)\in E,(v,w)\in E'_v,(u,w)\not\in E\)，当枚举到一个新的 \(w\) 时，就把 \((v,w)\) 这条边从 \(E'_v\) 中移除。根据经典结论“无向图中三元环的个数是 \(O(m\sqrt{m})\) 的”，这个做法的时间复杂度是 \(O(m\sqrt{m})\)。
注记：关键其实就在于，只包含一种边权的最短路是更简单的，所以需要分离 \(a\) 边和 \(b\) 边对答案的贡献。