| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 245 人关注过本帖
标题:C问题:巡回演出问题
只看楼主 加入收藏
ada121780200
Rank: 1
等 级:新手上路
帖 子:7
专家分:0
注 册:2011-4-19
收藏
 问题点数:0 回复次数:0 
C问题:巡回演出问题
Description

Flute市的Phlharmoniker乐团是一支非常优秀的管弦乐团,一直以来在国际古典乐坛上有着很高的地位。2000年的乐季又开始了,乐团在音乐总监C.M.R.和乐团指挥L.Y.M.的带领下到Harp市作一次大型演出。本着普及古典音乐的目的,L.Y.M决定在到达Harp市之前先在周围一些小城市做一段时间的巡回演出。此后的几天里,音乐家们将每天搭乘一个航班从一个城市飞到另一个城市,最后才到达目的地Harp市。请注意,由于乐团的演奏风格多样,适演曲目极多,所以乐团可以多次来到同一个城市进行演出。
虽然演出的酬劳相当可观,但还是要精打细算,尽量减少路费。可这并不容易,由于航线的费用和班次每天都在变。城市和城市之间都有一份循环的航班表,每一时间,每一方向,航班表循环的周期都可能不同。
经过整整一晚的思考,我们的音乐家终于想出了预定机票的最佳方案。你知道他们是怎么样做的吗?


Input

输入数据包含若干个场景。每个场景的描述由一对整数n(2<=n<=10)和k(1<=k<=1000)开始。音乐家们要在这n个城市里作巡回演出。城市用1,2,...,n编号,其中1是起点Flute市,n是终点Harp市,k是经过的天数。接下来将有n(n-1)份航班表,一份航班表一行,描述每对城市之间的航线和价格。第1组n-1份航班表对应从城市1到其他所有城市(2,3,...,n)的航班,接下来的n-1行是从城市2到其他城市(1,3,4,...,n)的航班,如此下去。
每份航班表由一个整数d(1<=d<=30)开始,表示航班表循环的周期。接下来的d个非负整数,表示1,2,...,d天对应的两个城市的航班的价格。价格为0表示那天两个城市之间没有航班。
例如,航班表“3 75 0 80”表示第1天的机票是75 KOI(KOI是信息学竞赛专用货币单位),第2天没有航班,第3天的机票是80 KOI,然后循环:第4天又是75 KOI,第5天没有航班,如此循环。
输入数据由n=k=0的场景结束。

Output

对输入的每个场景,如果乐团可能从城市1出发,每天都要飞往另一个城市,最后(经过k天)抵达城市n,则输出这k个航班的价格之和的最小值。如果不可能存在这样的巡回演出路线,则输出0。

Sample Input


3 6
2 130 150
3 75 0 80
7 120 110 0 100 110 120 0
4 60 70 60 50
3 0 135 140
2 70 80
2 3
2 0 70
1 80
0 0


Sample Output


460
0

搜索更多相关主题的帖子: 演出 管弦乐团 总监 
2011-04-19 16:35
快速回复:C问题:巡回演出问题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.042731 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved