UVA 590：Always on the Run - 航班調度 DP

問題描述

Trisha 需在 n 個城市（1 為巴黎起點，n 為亞特蘭大終點）中飛行 k 天，每天恰好飛一班航班，且不能連續兩天停留同一城市。每對城市間有周期性航班價格表（周期 d，給 d 天價格，0 表示無航班）。求最小總花費，或判斷無法在 k 天后到達城市 n。

DP 狀態定義

• dp[day][city]：第 day 天到達 city 的最小花費（day 從 0 到 k）。
• 初始：dp[0][1] = 0，其餘 -1（不可達）。

轉移方程

對於第 i 天 (1 ≤ i ≤ k)，對每個城市 j，若 dp[i-1][j] != -1，則嘗試飛往所有其他城市 to：

• 航班 j→to 的周期為 len，第 i 天對應價格索引 idx = (i-1) % len（或 1-base 調整）。
• 若價格 > 0，則 newCost = dp[i-1][j] + price，更新 dp[i][to] = min(dp[i][to], newCost)。

參考代碼 (C++)

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

const int MAXK = 1010, MAXN = 15;
int dp[MAXK][MAXN];
vector<int> cost[MAXN][MAXN]; // cost[u][v][day%period]

int main() {
    int n, k, tc = 0;
    while (scanf("%d%d", &n, &k) == 2 && (n || k)) {
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                cost[i][j].clear();
        for (int u = 1; u <= n; ++u) {
            for (int v = 1; v <= n; ++v) {
                if (u == v) continue;
                int d; scanf("%d", &d);
                cost[u][v].resize(d);
                for (int i = 0; i < d; ++i) scanf("%d", &cost[u][v][i]);
            }
        }
        memset(dp, -1, sizeof(dp));
        dp[0][1] = 0;
        for (int day = 1; day <= k; ++day) {
            for (int u = 1; u <= n; ++u) if (dp[day-1][u] != -1) {
                for (int v = 1; v <= n; ++v) if (u != v) {
                    int len = cost[u][v].size();
                    int idx = (day - 1) % len; // 0-based
                    int c = cost[u][v][idx];
                    if (c > 0) {
                        int nc = dp[day-1][u] + c;
                        if (dp[day][v] == -1 || nc < dp[day][v])
                            dp[day][v] = nc;
                    }
                }
            }
        }
        printf("Scenario #%d\n", ++tc);
        if (dp[k][n] == -1) printf("No flight possible.\n\n");
        else printf("The best flight costs %d.\n\n", dp[k][n]);
    }
    return 0;
}

複雜度

• 狀態數：k × n ≤ 1000 × 10 = 10⁴。
• 轉移：每狀態嘗試 n-1 個目標城市，總 O(k × n²) ≤ 10⁵，極快。

關鍵細節

• 航班價格 0 表示無航班，不可乘坐。
• 周期索引計算：第 1 天用索引 0，第 d+1 天又用索引 0。
• 不可達狀態保持 -1，避免溢出。