UVA 590
题意：
好长的题看了好久= =
有 n 个城市，编号 1~N， Trisha要坐飞机旅行 k 天，每天到一个城市，最后一天要到 N 城市。
也就是起点是城市1，第 k 天要到达 N 城市。求 k 天旅行的最小花费。
每个城市到其他城市都有一个航班表，x 天为周期，循环，接下来 x 个数表示航班价格。
多组输入，每组第一行输入 n 和 k；输入 0 0结束。
接下来 n(n-1)行，表示每个城市到其他城市的航班表。
也就是说第 i 个 (n-1)行， 表示 城市 i 到其余(n-1)个城市的航班表。
航班表第一个数表示周期天数，接下来每天的价格。
例如:
3 6 (n ,k n个城市，k 天。往下共 3*2行）
2 130 150 (城市1到城市2的航班 2 天为一周期，第一天130,第二天150，第三天130..循环...）
3 75 0 80 (城市1到城市3的航班 3 天为一周期，第一天75,第二天没有航班，第三天80..）
7 120 110 0 100 110 120 0 (城市2到城市1....
4 60 70 60 50 (城市2到城市3....
3 0 135 140 (城市3到城市1....
2 70 80
解题：
d[i][j] 表示 第 i 天到达第 j 个城市的最小花费。
p[i][j][q] 表示从 i 城市到 j 城市的第 q 个价格（因为会循环所以轮到第 q 个）；
那么 d[i][j] = min (d[i][j], d[i-1][k] + pri[k][j][q]);
就是 第 i 天到达第 j 个城市的最小花费等于
第 i-1 天到达第 k 个城市的花费加上 k 到 j 的花费与原来统计结果两者取小。
其中 j != k, 并且pri[k][j][q] != 0 (有航班可到达)，d[i-1][k] != INF (到达过k城市)；
#include <bits/stdc++.h> #define ll long long using namespace std;const int INF = 0x3f3f3f3f;int num[15][15], d[1010][15], pri[15][15][1010];int main() {int n, k, x, cas = 1;while (scanf ("%d%d", &n, &k) != EOF && (n || k)) {memset (pri, 0, sizeof (pri));for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j ++) {if (i == j) continue;scanf ("%d", &num[i][j]);for (int k = 1; k <= num[i][j]; k ++) {scanf ("%d", &pri[i][j][k]);}}}memset (d, INF, sizeof (d));d[0][1] = 0;for (int i = 1; i <= k; i ++) {for (int j = 1; j <= n; j ++) {for (int k = 1; k <= n; k ++) {if (j == k) continue;int q = (i-1) % num[k][j] + 1;if (pri[k][j][q] != 0 && d[i-1][k] != INF )d[i][j] = min (d[i][j], d[i-1][k] + pri[k][j][q]);}}}printf ("Scenario #%d\n", cas++);if (d[k][n] != INF)printf ("The best flight costs %d.\n\n", d[k][n]);else printf ("No flight possible.\n\n");}return 0; }