学步园

题意： 一个贼打算偷窃一副很贵很贵的画，于是现在要设计逃跑路线。他打算花k天时间，每天坐飞机从一个城市飞往另一个城市，第一天从城市1出发，第k天要求到达城市n。而飞机的价格每天都不一样(存在确定变化周期)，有的地方有的航线有时候会关闭，若不能找出这么一条k天的路线，输出“悲剧逃不掉”，否则输出买机票的最小费用。

解法： 设dp[k][i] 为第k天到达城市i的最小代价，于是有状态转移： 

dp[k][i] = min(dp[k][i], dp[k-1][j] + cost)，其中城市j与城市i在第k天有航班，cost为第k天从j到i的代价。

/* **********************************************
Author      : Nero
Created Time: 2013-8-27 23:41:38
Problem id  : UVA 590
Problem Name: Always on the run
*********************************************** */

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define REP(i,a,b) for(int i=(a); i<(int)(b); i++)
#define clr(a,b) memset(a,b,sizeof(a))

const int INF = 0x3f3f3f3f;
int dp[1010][11];
int g[33][11][11];
int rd[11][11];
int n,m;

int main() {
    int ca = 0;
    while(~scanf("%d%d", &n, &m), n || m) {
        clr(g,0);
        clr(dp,INF);
        dp[0][1] = 0;
        for(int i = 1; i <= n; i ++) {
            for(int j = 1; j <= n; j ++) if( i != j) {
                scanf("%d", &rd[i][j]);
                for(int k = 0; k < rd[i][j]; k ++) {
                    scanf("%d", &g[k][i][j]);
                }
            }
        }
        printf("Scenario #%d\n", ++ca);
        for(int k = 1; k <= m; k ++) {
            for(int i = 1; i <= n; i ++) {
                for(int j = 1; j <= n; j ++) if(i != j) {
                    int cost = g[(k-1)%rd[j][i]][j][i];
                    if(cost == 0) continue;
                    dp[k][i] = min(dp[k][i], dp[k-1][j] + cost);
                }
            }
        }
        if(dp[m][n] == INF) printf("No flight possible.\n");
        else printf("The best flight costs %d.\n", dp[m][n]);
        printf("\n");
    }
    return 0;
}