题解 P3547 【[POI2013]CEN-Price List】

· · 题解

\texttt{Solution}

考虑最短路的形式

显然只有3种情况：

全a，全b（末尾有1个a），全b（通过多走几条边使得完全去除a边）

第一种对应 2a\leq b，二三种为 b<2a，根据 b 究竟有多小决定是情况二还是情况三

前两种情况我们容易处理，跑一边bfs即可（0/1最短路）

最后一种情况我们考虑类似0/1最短路的转移

记 dis_x 为 k\to x 的距离

当用点 u 更新最短路是

枚举 u 一条边能到达的点 v，再枚举 v 一条边能到达的点 w，满足 u,w 间没有边,用 u 转移 w 即可

这个做法的复杂度为 O(\sum_{v}d_v^2)=O(m^2)

我们考虑我们第二次枚举的边 (v,w) 决定了我们要更新 w

事实上该条边作为第二条枚举的边有效更新只有这一次，实现时我们可以在边集中删去它

原因是考虑之后的点 x，一定有 dis_x\geq dis_u，所以之后边 (v,w) 的更新都是无效的

考虑只有3元环被遍历时不会删去边，每个三元环只会被遍历 O(1) 遍，三元环的个数为 O(m\sqrt m)

故复杂度为 O(m\sqrt m)

代码