2655.坐车回家-浙软预推免

通过数:22提交数:50学校:浙江大学保研机试真题 题目列表 标签
题目描述 小明需要乘坐列车回家,但有时可能一车不会到家,需要换乘。例如,有两列车的时刻表: 1号车: 1200 1300 1400 1500 1600 -1 2号车: -1 -1 1500 1600 1700 1800 其中-1表示该车不停靠该城市。因此小明需要1200坐1号车,在3号城市换乘2号车,可以在1800到家。 假设: 1. 一辆车的到站和驶离都是同一时刻(即列车到达城市后立即驶离,停留时间为0) 2. 小明换乘需要5分钟时间,也就是如果1400到达一个城市,1405之前发车无法换乘、1405及之后发车可以换乘 3. 每趟列车的时刻表由多个整数表示(HHMM格式),表示该列车在每个城市的到站时刻 4. 城市编号从1到n,小明从城市1出发,要到城市n回家 5. 旅程不能跨越天(即所有时间在00:00到23:59之间) 小明需要在最早到家的前提下,尽可能晚出发。请编写一个程序,根据给定的列车时刻表,计算出小明最早到家和最晚出发的时刻。 几何约束与换乘规则: 1. 时间表示: 输入时间以HHMM格式表示(如1200表示12:00,5表示00:05) 保证输入时间合法(00 ≤ HH ≤ 23,00 ≤ MM ≤ 59) 同一列车的时刻从城市1到城市n严格递增 2. 换乘规则: 如果小明在时间T到达某城市,则他只能换乘在时间T+5或之后到达该城市的列车 3. 目标: 首要目标:最小化到达城市n的时间 次要目标:在满足首要目标的前提下,最大化从城市1出发的时间 输入格式 第一行包含两个正整数n和m,分别表示城市的数量和列车的数量(1 ≤ n, m ≤ 10) 接下来的m行,每行包含n个整数,表示该列车在每个城市的到站时刻(HHMM格式)。 如果该车不停靠该城市,则用-1表示。 保证同一列车的时刻是严格递增的(即从城市1到城市n,时间递增) 输出格式 输出两个整数,分别表示小明最早到家的时刻和最晚出发的时刻(HHMM格式),用空格分隔 如果无法到家,输出 "IMPOSSIBLE" 输入样例1 3 3 1000 1100 -1 930 1030 1200 -1 1050 1150 输出样例1 1150 930 输入样例2 5 3 800 900 1000 1100 -1 -1 830 930 1030 1200 -1 -1 915 1015 1115 输出样例2 IMPOSSIBLE
C
补全
点击调试按钮即可调试代码。

点击提交按钮即可提交代码。