编程介的小学生 2019-12-31 17:42 采纳率: 20.5%
浏览 91

Hurry Up 怎么解决的呢

Problem Description
Now I'm in my school and I want to go back home as on time. However my bicycle has been stolen, which means I have to take buses. Let's consider the bus-net as a diagram. Vertices of the diagram (numbered 1, 2,..., N), correspond to stations, edges (pi != pj), denote that there is a direct connections from the station pi to the station pj (1<= pi, pj <= N). Transportation lines are numbered 1, 2,..., K. The L-th transportation line is defined as a series of stations pL,1, pL,2,..., pL,sL, on which vehicles of the L-th line stop, and durations rL,1, rL,2,...,rL,sL-1 of traveling between stations--- rL,1 is the time necessary to get from the station pL,1 to the station pL,2, or vice versa (i.e. from the station pL,2 to the station pL,1); rL,2 is the time necessary to get from the station pL,2 to pL,3, etc. All the stations of a line are different (i.e. i != j, implies pL,i != pL,j). In the L-th transportation line, buses run with certain frequency cL, and cL is a number from the set {6, 10, 12, 15, 20, 30, and 60}. The buses in the L-th transportation line, start from the station pL,1 at each hour of the day and night, g:0, (0<= g <=23), and then according to the frequency of the line i.e. at g:cL, g:2cL,... etc. (g:cL means cL minutes after hour g). Buses of the L-th line run in two directions: from the station pL,1 to pL,sL, and from the station pL,sL to pL,1. The hours of departure of the buses of the L-th transportation line from the station pL,sL are the same as from the station pL,1. In such a bus-net, we want to have a trip from the start station X which is near my school to the finish station Y which is near my home. During the trip one can change transportation lines, if he/she wants to. Say, the time of a change is equal to 0, however, while changing the line we have to take under consideration the time of waiting for the bus that we want to get into. Because of my poor memory, I can only change the line in no more than T (1<= T <= 20) times. And your task is to find a way from the start station X, to the finish station Y in W (0<= W <= 1440) minutes and change the lines as few as possible, if there are many ways to go back home and change the same least times of bus, choose the quickest one.

Input
In the first line there are written 8 integers, separated by single spaces:
N (1<= N <=200, number of stations), K (1<= K <=300, number of lines), X (1<= X <=N, the start station), Y (1<= Y <=N, X != Y, the finish station), GX (0<= GX <=23, the hour of the beginning of the trip), MX (0 <= MX <= 59, the minute of the beginning of the trip), W (0<= W <= 1440, the minute you must go back home within), T (1<= T <= 20, the times of changing line).

The stations are numbered from 1 to N, the transportation lines from 1 to K. In the following 3K lines the transportation lines are described - the description of each of them takes three consecutive lines.

In the first line describing the L-th transportation line, there are written two integers, separated by a single space: sL, the number of stations (2<= sL <=N), and cL - the frequency with which the vehicles run (cL belongs to: {6, 10, 12, 15, 20, 30, 60}).

In the second line describing the L-th transportation line, there are sL different integers, separated by single spaces: pL,1,pL,2,...,pL,sL --- the numbers of consecutive stations on the transportation line NO. L (1<= pL,i <=N, for 1<= i <=sL).In the third line describing the L-th transportation line, there are written sL-1 integers separated by single spaces: rL,1, rL,2,..., rL,sL-1 --- the times (in minutes) necessary to go between the consecutive stations of this transportation line (1<= rL,i <=240, for 1<= i <=sL-1).
The total number of stations on all transportation lines is not greater than 4000 (i.e. s1+s2+...+sK <= 4000).

Output
Your program should write in the only line with three integers, separated by a single space: the least times you change the lines, the hour of the earliest possible arrival to the finish station GY (0<= GY <=23) and the minute of the earliest possible arrival to the finish station MY (0<= MY <=59). If I can't go back home within W minutes anyway, puts "NO" in a single line.

Sample Input
6 2 5 6 23 30 1440 20
4 15
1 3 4 6
9 12 10
4 20
5 3 4 2
11 17 11

Sample Output
1 0 16

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 求差集那个函数有问题,有无佬可以解决
    • ¥15 MATLAB动图问题
    • ¥15 【提问】基于Invest的水源涵养
    • ¥20 微信网友居然可以通过vx号找到我绑的手机号
    • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
    • ¥15 解riccati方程组
    • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
    • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
    • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
    • ¥50 树莓派安卓APK系统签名