【BZOJ1003】【DP】【最短路】物流运输

一开始把这道题想得有点复杂。因为可能有很多种情况，比如k值很大每次都用次短路结果最优，或者k值很小每次都用最短路结果最优，如果还要变化的话就更复杂了。但其实后来一想，我们只需要暴力枚举出每一段时间，用cost(s,t)表示在[s,t]这段时间中的最小费用，然后DP：f[i] = min(cost(1,i),f[j] + cost(j+1,i) + k)一开始把这道题想得有点复杂。因为可能有很多种情况，比如k值很大每次都用次短路结果最优，或者k值