题意分析

题目背景
艺术大盗Trisha需要从巴黎（城市1）出发，经过k天的飞行，每天飞往不同的城市，最终到达亚特兰大（城市n）。每个城市之间的航班价格有周期性变化，我们需要找到总花费最小的路线。

输入要求

• 城市数量n（2 ≤ n ≤ 10）和飞行天数k（1 ≤ k ≤ 1000）
• 每个城市对的航班周期d（1 ≤ d ≤ 30）和d天的价格（0表示无航班）

输出要求

• 若能找到满足条件的路线，输出最小总花费
• 否则输出不可能

解题思路

1. 动态规划状态定义

   • dp[day][city]表示第day天到达city的最小总花费

2. 状态转移

   • 对于每一天day（1到k）
   • 对于每个目标城市to（1到n）
   • 遍历所有可能的出发城市from（1到n，且from != to）
   • 计算从from到to在第day天的航班价格（考虑周期性）
   • 更新dp[day][to]的最小值

3. 周期处理

   • 使用模运算(day-1) % period获取当天的实际价格

4. 边界条件

   • 第0天只在巴黎（城市1），花费为0
   • 其他状态初始化为无穷大

5. 结果判断

   • 检查第k天是否能到达亚特兰大（城市n）

正确代码

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

const int INF = INT_MAX / 2;

struct Flight {
    int d;
    vector<int> costs;
};

void solve_scenario(int n, int k, vector<vector<Flight>>& schedules) {
    // dp[day][city] = 最小成本
    vector<vector<int>> dp(k + 1, vector<int>(n + 1, INF));
    dp[0][1] = 0;  // 第0天在巴黎(城市1)

    for (int day = 1; day <= k; day++) {
        for (int from = 1; from <= n; from++) {
            if (dp[day - 1][from] == INF) continue;
            
            for (int to = 1; to <= n; to++) {
                if (from == to) continue;  // 不能停留在同一城市
                
                const Flight& flight = schedules[from - 1][to - 1];
                int cost = flight.costs[(day - 1) % flight.d];
                if (cost == 0) continue;  // 当天无航班
                
                if (dp[day][to] > dp[day - 1][from] + cost) {
                    dp[day][to] = dp[day - 1][from] + cost;
                }
            }
        }
    }

    if (dp[k][n] != INF) {
        cout << "The best flight costs " << dp[k][n] << "." << endl;
    } else {
        cout << "No flight possible." << endl;
    }
}

int main() {
    int scenario = 1;
    while (true) {
        int n, k;
        cin >> n >> k;
        if (n == 0 && k == 0) break;

        vector<vector<Flight>> schedules(n, vector<Flight>(n));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                cin >> schedules[i][j].d;
                schedules[i][j].costs.resize(schedules[i][j].d);
                for (int m = 0; m < schedules[i][j].d; m++) {
                    cin >> schedules[i][j].costs[m];
                }
            }
        }

        cout << "Scenario #" << scenario++ << endl;
        solve_scenario(n, k, schedules);
        cout << endl;
    }
    return 0;
}