网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[POI1997]便宜的旅行
成绩 | 0 | 开启时间 | 2013年01月22日 星期二 09:05 |
折扣 | 0.8 | 折扣时间 | 2013年01月22日 星期二 09:05 |
允许迟交 | 是 | 关闭时间 | 2013年01月22日 星期二 09:05 |
输入文件 | tan.in | 输出文件 | tan.out |
坐马车来进行横穿大陆的旅行一般都要花去几天的时间,所以路上在旅馆的住宿费用是很大的一笔开销。为了使旅行的安全和舒适,人们只在白天赶路,并且每天最多只能走800公里。在旅途中时,车夫和旅客们都是在旅馆中度过晚上的(不包括起点和终点)。现在我们想要尽可能的减少在路上的开销,就是在旅馆中的住宿费用(即使增加了花在路上的时间也无所谓)。由于旅行是在一条高速公路上进行的,所以旅途是单向并且没有分叉的,也就是马车只经过路上的每个点一次。现给出每个旅馆距离起点的距离和一个人(包括车夫和旅客)在旅馆住一个晚上的费用。我们假设在路上的每个点最多都只能有一个旅馆,在起点和终点的住宿是不用花费的。并且保证每800公里必然有一个旅馆,也就是说,这样的旅行必然是可以实现的。
任务
请写一个程序
在文本文件中读入路程的总长度、旅馆的数目和对旅馆的描述;
找出两个旅行的方案:
一个最便宜的方案(就是付出的宿费最少的方案);如果有多个方案,选择在旅馆中度夜的次数最少的方案;
一个最短的方案(就是在旅馆中度夜的次数最少的方案);如果有多个方案,选择花费最少的方案;
把结果,就是两个旅行方案,最便宜和最短的旅行方案,输出到文件中。
输入格式:
在文本文件的第一行包括两个用空格分开的正整数。第一个整数d为从起点到终点的距离,第二个整数h为旅馆的数目,d <= 16000,h <= 1000。以下的h行每行两个整数,为对旅馆的描述。每行中的第一个整数为旅馆距离起点的距离,第二个为旅馆的住宿费用,为不大于1000的整数。数据是按照据起点距离递增的顺序排列的。
输出格式:
你应该在文本文件中输出最便宜的旅程方案。也就是说,从起点开始需要过夜的旅馆距离起点的距离。类似的,你应该在文件的第二行输出最短的旅程方案。所有的整数应该的用空格分开。
样例:
输入
2000 7
100 54
120 70
400 17
700 38
1000 25
1200 18
1440 40
输出
400 1200
400 1200