题面
题意
有 \(m\) 个码头，要规划 \(n\) 天内从 \(1\) 号码头到 \(m\) 号码头的航线，有 \(e\) 条连接 \(u,v\)，每日花费为 \(w\) 的双向航线，其中每个码头会有一些时间不可到达，同时如果在某一天要改变前一天的航线会额外花费 \(k\)，求 \(n\) 天可能的最小花费。
题解
题意相当复杂，实际由于 \(n,m\) 非常小，可以暴力求出每一对 \(l,r\)，从第 \(l\) 天到 \(r\) 天都可以使用的边是哪些，再求出从第 \(l\) 天到 \(r\) 天不改变航线的最小花费，令其为 \(cost(l,r)\)。之后只需要用区间 DP 求出从第 \(l\) 天到第 \(r\) 天允许改变航线的最小花费，转移方程为：\(dp[l][r]=\min(cost(l,r),\min_{i=l}^{r-1}(dp[l][i]+dp[i+1][r]+k))\)。
注意计算最小花费时要乘上 \(r-l+1\)，这个过程中注意不要爆 long long。