投递最佳路线(BestDeliver)
   
[问题描述]

　　某投递公司需要在各个车站间运送包裹。某位司机运送一个包裹到某站后，再将该站待运包裹送到下一站。一个可以运送的包裹是指可被某司机运送到目的地而不超过司机的工作时间范围的包裹。司机的工作时间由他开始运送第一个包裹算起，到选送完最后一个包裹为止。公司希望司机在工作时间内尽可能多送包裹。

　　程序设计要求为司机找出单个工作日内的最佳路线。司机最初的出发地都为A站，司机运送包裹有如下条件：

　　(1)司机工作时间不超过10小时，但不限开始工作的时间。
　　(2)每个包裹都有一个计划运送时间，在此时间之前则包裹尚未出现。
　　(3)司机在A站开始运送的第一个包裹，应是A站末被运送包裹中的最早出现的一个。
　　(4)一次只能运送一个包裹，途中不准放下，而且，包裹必须从指定的起点站运送到终点站，途中不得经过其他站。如果在某站中暂时没有可运送包裹，则他会去另一个有可运送包裹的站送包裹(空车行走时间不计入运送时间)。司机也可以等某车站的任一个末被运送包裹。
　　(5)选择路线时，应选择累计运送时间最长的那条路线。若有多条路线累计最长运送时间相等，则选择使司机有最短工作时间的那条路线。
　　(6)A站包裹一定要运送，且运完A站包裹即可，其他站的包裹则不一定要运送。
　　在A站运送第一个可运送包裹的司机的最佳路线，要在考虑下一个司机前确定，如此类推直到A站所有包裹都被按计划运送。不能运送包裹要报告出来。

[输入格式]

　　从键盘输入两个文本文件的文件名。第一个为输入数据文件名，第二个为输出结果文件名。所有文件每一行中的分隔符均为单个空格，行的分隔符均为单个回车。
　　第一行有一个整数n（1≤n≤500），表示包裹的数量。
　　接下来n行中每一行描述一个包裹的情况，格式为：
　　　　包裹标识号　起点站　终点站　时间
　　其中包裹标识号为自然数，站名为单个大写字母，时间指包裹计划运送时间，格式为hhmm(hh表示小时，mm表示分钟)。
　　接下来一行有一个整数s(1≤s≤26)，表示站的总数。
　　接下来s*(s-1)/2行描述任意两站之间的运送时间，格式为：
　　　　站1　站2　时间
　　其中时间表示行走此两站所花的时间。

[输出格式]

　　D （所需司机数）
　　Q （Q表示司机1行走路段总数，以下Q行为这些路段的描述，再加两行有关时间）
　　n A B （包裹#n从A运到B，若n=0表示空车从A到B）
　　……
　　hhmm （总运送时间）
　　hhmm （总工作时间）
　　…… （其他司机运送路线和时间）
　　P （P表示不能运送包裹总数，以下P行为这类包裹的描述）
　　n B （B站包裹#n不能被运送）

[输入输出样例]

　　

   

 
网站导航 | 关于曙光 | 联系我们 | 请提意见
Copyright © FuJian Sunshine Educational Info. Co.,Ltd.
福建曙光教育资讯有限公司 版权所有