|
|
|
|
|
塞内加尔的世界杯
|
||||
【背景】 相信大家都看了昨天韩日世界杯开幕赛上塞内加尔队的精彩表现！ 塞内加尔是西非的一个小国家，你也许很难在世界地图上找到它，甚至你有可能从未听说过它--它实在是个太小、太贫穷的国家了。可是，就是这个人口不足900万、全国仅有2个标准足球场地的小国，在2002韩日世界杯的非洲区预选赛中脱颖而出，取得了世界杯决赛圈的入场券（幸好，中国队也进入了世界杯决赛圈，不然可就丢脸了）。 塞内加尔全国球迷欣喜若狂，世界足球行家大跌眼镜的同时，塞内加尔足协却发现自己面临着一个颇为尴尬的问题--说起来令人不可思议，由于打非洲区预选赛时四处征战，加上足协经营不力，现在足协的预算以几近赤字--也就是说，塞内加尔足协支付不起从本国乘飞机到达韩国参加世界杯的费用！经过三思，塞内加尔足协向非洲足联递交了一份《关于减免球队旅行费用》的申请；可是众所周知，非洲足联也是"清水衙门"，幸好非洲足联秘书长神通广大，弄来了M张优惠乘机券：每张优惠券可以作用于一条航线，使全队通过此航线的费用减半；多张优惠券用于同一条线路，其效果叠加--即在一条航线上用两张优惠券，其费用降为原费用的1/4，依此类推。 【问题】 塞内加尔足球队要从塞内加尔国家机场出发，途经一些中转机场，最后要到达韩国釜山机场。为了合理地分配各张优惠券，使得所需费用最少，塞内加尔足协找到了你，请你编程解决这个问题。 【输入】 第1行有两个数N、M（0<N<=70，0<=M<=20）并用空格隔开，分别表示包括起点（塞内加尔国家机场）、终点（韩国釜山机场）的机场数，以及塞内加尔足协现有的优惠券数量。 从第2行到第N+1行起，每行有N个数，其中第I行的第J个数代表从机场I到机场J所需费用；为零的数代表两机场无航线。 假设起点标号为1，终点标号为N。 【输出】 第1行仅有一个数（保留两位小数），代表所求得的从机场1到机场N的最小费用； 第2行打印航线，每两个机场间用"->"连接（参见样例输出）； 输入数据保证从塞内加尔机场可达釜山机场。 【样例输入】 5 2 0 0 80 96 0 70 0 72 54 0 18 0 0 99 82 72 18 71 0 0 69 0 0 70 0 【样例输出】 81.00 1->3->5 |
||||
| 网站导航
| 关于曙光 | 联系我们
| 请提意见 Copyright © FuJian Sunshine Educational Info. Co.,Ltd. 福建曙光教育资讯有限公司 版权所有 |