HDU 5168：Legal path——邊權差約束最短路

題目描述

有向圖 n≤1e5, m≤2e5，邊權 z≤1e9。合法路徑：相鄰邊權差 ≥ K。求 1→n 最短合法路徑長度（邊權和）。

核心思想：按邊權排序 + DP

邊權大的不可能接在小的後面（差值需 ≥ K）。將邊按權值升序排序，依次處理。對每條邊 u→v 權 c，從 u 的狀態中找權值 ≤ c-K 的最優轉移。

狀態維護

dp[v]：到達 v 的合法路徑集合，存 (最後邊權, 總長度) 對，保持 邊權遞增、總長度遞減 的凸包性質。

轉移

• 在 dp[u] 中二分查找最大邊權 ≤ c-K 的記錄
• 用其總長度 + c 更新 dp[v]：若新總長度 < 當前同邊權或更大邊權的長度，則加入並清理被支配點

C++ 實現（關鍵）

struct Edge { int u,v; long long w; } E[200005];
vector<pair<long long,long long>> dp[100005]; // (w, dist)

bool cmp(Edge a, Edge b) { return a.w < b.w; }

int main() {
    int T; scanf("%d",&T);
    while(T--) {
        int n,m; long long K; scanf("%d%d%lld",&n,&m,&K);
        for(int i=1;i<=n;++i) dp[i].clear();
        for(int i=0;i w)
                    dp[v].push_back({w,w});
            } else if(!dp[u].empty()) {
                // 二分查找 dp[u] 中 w-K
                auto it = upper_bound(dp[u].begin(), dp[u].end(), make_pair(w-K, LLONG_MAX),
                    [](auto& a, auto& b){ return a.first < b.first; });
                if(it != dp[u].begin()) {
                    --it;
                    long long ndist = it->second + w;
                    if(dp[v].empty() || dp[v].back().second > ndist)
                        dp[v].push_back({w, ndist});
                }
            }
        }
        if(dp[n].empty()) puts("-1");
        else printf("%lld\n", dp[n].back().second);
    }
    return 0;
}

複雜度

• 排序：O(m log m)
• 每條邊二分 + 攤銷 O(1) 維護凸包：O(m log m)