BZOJ 物流運輸路線規劃：DP + SPFA 預處理 + 線段樹優化

問題描述

n 天內將貨物從碼頭 A 運到 B，每天可能某些碼頭不可用。需制定 n 天運輸計劃，每天選一條路線，修改路線有成本，求最小總成本。

解題思路

動態規劃：dp[i] 表示前 i 天最小成本。轉移：dp[i] = min_{j，其中 cost(a,b) 為第 a 到 b 天共用一條路線的最小成本（需滿足每天路線可用）。預處理所有區間 cost：對每一天跑 SPFA 求最短路，再用 RMQ 或線段樹合併？實際上可預處理每天的最短路，區間成本為該區間內每天最短路的最大值（因路線需固定，取能覆蓋所有天的最短路）。具體建模視具體題目約束而定。

// 伪代碼框架
for i = 1..n:
    dp[i] = INF
    for j = 0..i-1:
        dp[i] = min(dp[i], dp[j] + K + cost[j+1][i])
// cost 預處理：對每個起點跑 SPFA，或對每個區間二分求可行路線