UVa 590 Always on the run（简单链式DP）

题意：

有n座城市，Trisha要求在这n座城市旅游k天，从城市1出发，第k天到达城市n。

输入有n*(n-1)行，每n-1行代表i到除了i之外的其他城市航班的天数以及价格。

求出Trisha的最小花费。

思路：

链式dp，dp[i][d]代表第d天到达i城市所需要的最小代价，于是dp[i][d] = min(dp[i][d], dp[j][d-1] + price[j][i][X])。

意思是：第d天到达i城市所花费的代价是，第d-1天到达j城市 + j到i的价格 最小的一个。

由于初识状态只有一个，即从城市1出发。所以初始值只有一个dp[1][0] = 0。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>

#define min(a,b) (((a) < (b)) ? (a) : (b))

int day[15][15];
int price[15][15][35];
int dp[15][1005];

int main()
{
    int n, k;
    int cases = 0;
    while (scanf("%d %d", &n, &k) && n && k)
    {
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                if (i != j) 
                {
                    scanf("%d", &day[i][j]);
                    for (int d = 1; d <= day[i][j]; ++d)
                        scanf("%d", &price[i][j][d]);
                }
        
        for (int i = 0; i <= n; ++i)
        {
            for (int d = 0; d <= k; ++d)
                dp[i][d] = INT_MAX;
        }
        dp[1][0] = 0;

        for (int d = 1; d <= k; ++d)
            for (int i = 1; i <= n; ++i)
                for (int j = 1; j <= n; ++j)
                    if (i != j)
                    {
                        int q = (d - 1) % day[j][i] + 1;
                        if (price[j][i][q] && dp[j][d-1] != INT_MAX)
                            dp[i][d] = min(dp[i][d], dp[j][d-1] + price[j][i][q]);
                    }

        printf("Scenario #%d\n", ++cases);
        if (dp[n][k] != INT_MAX)
            printf("The best flight costs %d.\n\n", dp[n][k]);
        else
            printf("No flight possible.\n\n");
    }
    return 0;
}