Posted on 2008-06-01 10:24
superman 阅读(219)
评论(0) 编辑 收藏 引用 所属分类:
ZOJ
1 /* Accepted 1250 C++ 00:00.02 904K */
2 #include <iostream>
3
4 using namespace std;
5
6 struct { int cnt, cost[32]; } map[12][12];
7
8 int main()
9 {
10 int n, m, c = 1;
11 while(cin >> n >> m && n && m)
12 {
13 for(int i = 1; i <= n; i++)
14 for(int j = 1; j <= n; j++)
15 if(i != j)
16 {
17 cin >> map[i][j].cnt;
18 for(int k = 1; k <= map[i][j].cnt; k++)
19 cin >> map[i][j].cost[k];
20 }
21
22 int opt[1001][12];
23 for(int i = 0; i <= m; i++)
24 for(int j = 0; j <= n; j++)
25 opt[i][j] = INT_MAX;
26 opt[0][0] = opt[0][1] = 0;
27
28 for(int i = 1; i <= m; i++)
29 for(int j = 1; j <= n; j++)
30 for(int k = 1; k <= n; k++)
31 if(j != k)
32 if(opt[i - 1][k] != INT_MAX)
33 {
34 int p;
35 if(i % map[k][j].cnt == 0)
36 p = map[k][j].cnt;
37 else
38 p = i % map[k][j].cnt;
39 if(map[k][j].cost[p] == 0)
40 continue;
41 opt[i][j] <?= opt[i - 1][k] + map[k][j].cost[p];
42 }
43
44 cout << "Scenario #" << c++ << endl;
45 if(opt[m][n] != INT_MAX)
46 cout << "The best flight costs " << opt[m][n] << '.' << endl;
47 else
48 cout << "No flight possible." << endl;
49 cout << endl;
50 }
51
52 return 0;
53 }
54