# Travelling Plan problem dilemma

Hello everyone. I am totally new to Codechef. I would rather say I am below novice level. So I went on to practice my first problem [Traveling Plan][1]. I would like to know if I assumptions are right:

1. There are N Bus Stations
2. There are M Buses
3. Every Bus is repsented by the set (U, V, S, E) where U is the Source, V is the Destination and S is the time the bus will start from U and E is the time the bus will arrive at V (no intermediate stations)
4. Given the dead line T, the chef must be at the bus station N before or at the time T
5. The other things are fine and I agree with the constraints too
6. Now, the problem I facing here is with regarding the Input and the Output:

5 10 5

1 2 1 2

1 5 3 4

2 4 4 5

2 5 5 6

4 5 6 7

### Output:

2

Here, to my knowledge, the bust will start at station 1 at time 2 and reach station 1 again at time 2??? I drew a graph, excluding this input as:

1. edge from 1 to 3 weight 9 (5+4 total time)
2. edge from 2 to 4 weight 9 (4+5 total time)
3. edge from 2 to 5 weight 11 (6+5 total time)
4. edge from 4 to 6 weight 12 (5+7 total time)

Are my assumptions correct? I thing I am definitely sure is that it is a problem similar to shortest path traversal or Travelling Salesperson. But Don’t know where am I struck? Please help
[1]: http://www.codechef.com/problems/TABUS

Your question is too difficult it needs proper attention of mind but don’t worry i will get you back later with relevant answer. Thanks for this tough question… smm india

you took it wrong , check the input format its as follows:-
starting_station ending_station starting_time ending_time
so the bus will start at station 1 at time 1 and reach station 2 again at time 2
Further its in no way related to Travelling salesman problem . Don’t assume on the basis of name of the problem

1 Like