Time table

You are the owner of railway system between n cities, numbered by integers from 1 to n. Each train travels from the start station to the end station according to a very specific timetable(always on time),not stopping anywhere between. On each station a departure timetable is available. Unfortunately each timetable contains only direct connections. A passenger that wants to travel from city p to city q is not limited to direct connections however-he or she can change trains. Each change takes zero time, but a passenger cannot change from one train to the other if it departs before the first one arrives. People would like to have a timetable of all optimal connections. a connection departing from city p at A o’clock and arriving in city q at B o’clock is called optimal if there is no connection that begins in p not sooner than at A, ends in q not later than at B, and has strictly shorter travel time than the considered connection. We are only intrested in connections that can b completed during same day.

TASK:

Write a program that :

• Reads the number n and departure timetable for each of n cities from the standard input,

• Creates a timetable of optimal connections from city 1 to city n,

• Writes the answer to the standard output.

Input:

The input begins with the integer t, the number of test cases. Then t test cases follow.

For each test case the first line of the input contains an integer n (2<=n<=100000).the following lines contain n timetables for cities 1,2,…,n respectively.

The first line of the timetable description contains only one integer m. Each of the following m lines corresponds to one position in the timetable and contains:departure time A, arrival time(A<B) and destination city number t (1<=t<=n) separated by single spaces. Departure time A and arrival time B are written in the format hh:mm, where hh are two digits representing full hours (00<=hh<=23) and mm are two digits representing minutes (00<=mm<=59).Positions in the timetable are given in non-decreasing order according to the departure times. The number of all positions in all timetables does not exceed 1000000.

Output:

For each test case the first line of the output contains an integer r – the number of positions in the timetable being the solution. Each of the following r lines contains a departure time A and an arrival time B separated by single space .the time format should be like in the output and positions in the timetable should be ordered increasingly according to the departure times. If there is more than one optimal connection with the same departure and arrival time, your program should output just one.

Example:

Sample input:

1

3

3

09:00 15:00 3

10:00 12:00 2

11:00 20:00 3

2

11:30 13:00 3

12:30 14:00 3

0

Sample output:

2

10:00 14:00

11:00 20:00

(please make for me i am very thankfull to if you solve this for me i am very tense ths is my home assignment in c++ which is of 60 numbers and i dnt want to loose it plz plz plz

thank you)

I think that you would learn more if you tried to do your own homework rather than asking someone else to do it for you. It's a bit unfair on your fellow students, isn't it?

no this is an open book task do how ever you want to do thts why no unfair wid any1

plz help me

If you can't do this assignment then that is telling you something - you need to learn a little more C++. Copying down a program that someone else writes for you isn't going to achieve that. You obviously have a problem so you should talk to your teacher so that he/she ensures you get the appropriate support. That's what education is about.

yeah but i have to submit it wid in 3 days thts y i have ni choice to take any 1 help

Talk to your teacher.

ijack has given you good advice and you would do well to take it.

Anyone doing your homework for you would not be doing you any favors. No one on this forum will do your homework for you.

jst help me what to do i will do it my self

can any 1 tell me its logic?

bhootni k khud mehnat kr salay kyn dosroon se zalil ho raha hai

Can anyone give him hint or something...

No point - it had to be submitted by 4th Feb.

Ask Your Question

Weekly Poll