您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

HDU 4751：最短路徑結合背包動態規劃解題詳解

編輯：關於C++

題目背景

Bob 厭倦了遊戲，獨自前往長沙旅遊。岳麓山、橘子洲、世界之窗、省博物館等都是他想打卡的景點，但時間有限，無法全數遊覽。假設長沙共有 N 個景點，每個景點擁有一個滿意度值 S_i，造訪可增加總滿意度。Bob 希望在限定時間 T 內，從景點 S 出發，選擇性造訪部分景點，最終抵達景點 E，使總滿意度最大化。造訪景點 i 需耗費 C_i 時間單位。特別的是，Bob 只會造訪滿意度 嚴格大於 上一次造訪景點的景點。路徑為雙向，也可選擇僅經過不造訪（不耗時、無滿意度）。

核心解題思路

全源最短路預處理：先用 Floyd-Warshall 算出任意兩景點間的最短路徑時間，將圖轉化為完全圖，邊權為最短時間。
按滿意度排序：因轉移條件要求下一景點滿意度嚴格大於當前，故將景點按滿意度遞增排序，確保 DP 狀態轉移時，所有可能的前驅狀態已計算完畢。
動態規劃定義：dp[i][t] 表示以第 i 個景點（排序後）為最後造訪點，耗時 t 所能獲得的最大滿意度。
狀態轉移：對每個景點 i，嘗試從所有滿意度較小的景點 j 轉移：dp[i][t + dist[j][i] + C[i]] = max(dp[i][...], dp[j][t] + S[i])。同時需考慮直接從起點 S 出發、或最終不造訪終點 E 的情況。
答案提取：在所有 dp[i][t] (t ≤ T) 中取最大值；若無法在 T 內抵達 E，輸出 0。

關鍵細節與陷阱

重邊處理：輸入可能有多條相同端點的路徑，建圖時保留最小權值。
起點、終點可不造訪：只作為路徑端點，不計滿意度與造訪時間。
時間限制 T ≤ 300，N < 100，狀態數約 100 × 300 = 30,000，轉移 O(N²T) 約 3×10⁶，完全可行。

複雜度分析

Floyd-Warshall：O(N³) ≈ 10⁶
DP 轉移：O(N²T) ≈ 3×10⁶
總時間記憶體均在限制內。

參考代碼片段 (C++)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 105;
int n, m, T, S, E;
int dist[MAXN][MAXN], dp[MAXN][305];
int C[MAXN], Sat[MAXN], id[MAXN];

struct Node { int c, s, id; bool operator<(const Node& o) const { return s < o.s; } } a[MAXN];

int main() {
    int cas = 1;
    while (scanf("%d%d%d%d%d", &n, &m, &T, &S, &E) == 5) {
        for (int i = 0; i < n; ++i) scanf("%d", &C[i]);
        for (int i = 0; i < n; ++i) scanf("%d", &Sat[i]);
        for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) dist[i][j] = (i==j?0:INF);
        for (int i = 0; i < m; ++i) {
            int u, v, w; scanf("%d%d%d", &u, &v, &w);
            dist[u][v] = dist[v][u] = min(dist[u][v], w);
        }
        // Floyd
        for (int k = 0; k < n; ++k)
            for (int i = 0; i < n; ++i)
                for (int j = 0; j < n; ++j)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
        // 準備排序
        for (int i = 0; i < n; ++i) a[i] = {C[i], Sat[i], i};
        sort(a, a + n);
        for (int i = 0; i < n; ++i) id[a[i].id] = i;
        // DP 初始化
        memset(dp, -1, sizeof(dp));
        int start = id[S], finish = id[E];
        // 直接從 S 走到 E 不造訪任何景點
        int ans = (dist[S][E] <= T) ? 0 : -1;
        // 以每個景點為首個造訪點
        for (int i = 0; i < n; ++i) {
            int u = a[i].id;
            int cost = dist[S][u] + a[i].c;
            if (cost <= T) dp[i][cost] = a[i].s;
        }
        // DP 轉移
        for (int i = 0; i < n; ++i) {
            for (int t = 0; t <= T; ++t) if (dp[i][t] != -1) {
                // 嘗試以 i 為最後點直接走到 E
                if (t + dist[a[i].id][E] <= T) ans = max(ans, dp[i][t]);
                // 轉移到滿意度更高的景點 j
                for (int j = i + 1; j < n; ++j) {
                    int nt = t + dist[a[i].id][a[j].id] + a[j].c;
                    if (nt <= T) dp[j][nt] = max(dp[j][nt], dp[i][t] + a[j].s);
                }
            }
        }
        printf("Case #%d: %d\n", cas++, max(ans, 0));
    }
    return 0;
}