P1850

先用 Floyd 预处理出任意两点之间的最短路 \(\operatorname{dis}(u,v)\)，然后 dp。

设 \(f_{i,j,0/1}\) 表示考虑前 \(i\) 门课，有 \(j\) 门课换教室，第 \(i\) 节课是否换教室的答案。

转移就按照第 \(i\) 次换不换与第 \(i-1\) 次换不换分类：

\[\begin{cases} f_{i,j,0}=\min\{f_{i-1,j,0}+\operatorname{dis}(c_{i-1},c_i),f_{i-1,j,1}+k_{i-1}\cdot\operatorname{dis}(d_{i-1},c_i)+(1-k_{i-1})\cdot\operatorname{dis}(c_{i-1},c_i)\}\\ f_{i,j,1}=\min\{f_{i-1,j-1,0}+k_i\cdot\operatorname{dis}(c_{i-1},d_i)+(1-k_i)\cdot\operatorname{dis}(c_{i-1},c_i),f_{i-1,j-1,1}+k_{i-1}k_i\cdot\operatorname{dis}(d_{i-1},d_i)+k_{i-1}(1-k_i)\cdot\operatorname{dis}(d_{i-1},c_i)+(1-k_{i-1})k_i\cdot\operatorname{dis}(c_{i-1},d_i)+(1-k_{i-1})(1-k_i)\cdot\operatorname{dis}(c_{i-1},c_i)\} \end{cases} \]