洛谷3547 [POI2013]CEN-Price List
Luogu 分析 显然最短路只有三种可能： 全走 $a$ 边。 把两条 $a$ 边看成一条 $b$ 边，如果还剩一条 $a$ 边就走 $a$ 边。 全走 $b$ 边。 前两种只需要简单 0/1 BFS 一遍即可，关键在于第三种如何处理。 有一个显然的 $\mathcal{O}(m^2)$ 思路是，枚举 $u$ 的出边 $v$ 和 $v$ 的出边 $w$，如果 $u,w$ 间没有连边就用 ...
Luogu 分析 显然最短路只有三种可能： 全走 $a$ 边。 把两条 $a$ 边看成一条 $b$ 边，如果还剩一条 $a$ 边就走 $a$ 边。 全走 $b$ 边。 前两种只需要简单 0/1 BFS 一遍即可，关键在于第三种如何处理。 有一个显然的 $\mathcal{O}(m^2)$ 思路是，枚举 $u$ 的出边 $v$ 和 $v$ 的出边 $w$，如果 $u,w$ 间没有连边就用 ...
Luogu LOJ 分析 首先要知道 显然我们可以 $O(C\log C)$ 预处理出 $f_a,f_b,f_c$ ，然而计算还是 $O(n^3)$ 的。 但是注意到 $O(n^3)$ 的枚举中会出现很多贡献为 $0$ 的情况： $\mu(x),\mu(y),\mu(z)$ 中有 $0$ 。 $\operatorname{lcm}(x,y)>A$ 或 $\operatorname{...