Travelling Plan problem dilemma

general
, ,
1

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:

    Input:

    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]: TABUS Problem - CodeChef

1 Like
2

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

3

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
4

Its very difficult question you asked. We need more time to reply of your this question. I will discuss it with my friends and let you know the answers. Offshore SEO Services

5

I was trying to solve a similar question in my hosting español site and not even with the help of my friends could get a good answer. The dificulty of the problem is the inputs. Too many parameters.

6

I was solving a sililar question.I will reply to you soon.

Vaibhav Malhotra
http://dormoto.com/
motorcycle rentals

7

Can you help me with this as well please Some More Homework - Wrong Answer - general - CodeChef Discuss