這題做得人特別少，但實(shí)際上就是很普通的動(dòng)態(tài)規(guī)劃。
思路：
由于飛到某個(gè)點(diǎn)的時(shí)候，后面的行程跟前面的行程沒有什么聯(lián)系，所以開一個(gè)二維數(shù)組 f[K][N]，
f[i][j] = { 從第 j 個(gè)點(diǎn)，第 i 個(gè)時(shí)刻開始飛行直到終點(diǎn)，所需要的最小花費(fèi) }
然后就從后往前推就可以了。
#include <stdio.h>
#include <string.h>
#define MAX_N 16
#define MAX_D 32
#define INFINITE 100000
struct node 
{
int arr[MAX_D], cnt;
};
struct node map[MAX_N][MAX_N];
int N, K;
__inline void input()
{
int i, j, k;
struct node *t;
for (i = 1; i <= N; i++) {
for (j = 1; j <= N; j++) {
if (i == j)
continue;
t = &map[i][j];
scanf("%d", &t->cnt);
for (k = 0; k < t->cnt; k++)
scanf("%d", &t->arr[k]);
}
}
}
__inline int min(int a, int b)
{
return a < b ? a : b;
}
__inline void solve(int sc)
{
int dp[2][MAX_N], *cur, *nxt, i, j, k, val;
struct node *t;
memset(dp, 0, sizeof(dp));
dp[0][N] = 1;
for (i = K - 1; i >= 0; i--) {
cur = dp[(K - 1 - i) & 1];
nxt = dp[(K - i) & 1];
for (j = 1; j <= N; j++) {
nxt[j] = 0;
for (k = 1; k <= N; k++) {
if (j == k || !cur[k])
continue;
t = &map[j][k];
val = t->arr[i % t->cnt];
if (!val)
continue;
val += cur[k];
if (!nxt[j] || val < nxt[j])
nxt[j] = val;
}
}
}
printf("Scenario #%d\n", sc);
if (nxt[1])
printf("The best flight costs %d.\n\n", nxt[1] - 1);
else
printf("No flight possible.\n\n");
}
int main()
{
int i;
freopen("e:\\test\\in.txt", "r", stdin);
for (i = 1; scanf("%d%d", &N, &K), N; i++) {
input();
solve(i);
}
}