parash93's blog

Shortest Path when there is a maximum possible time constraint as well
By parash93, 10 years ago, In English

How do we approach problems where while minimising the path from Source to Destination, we even have to keep the time of travel below a certain value? I am referring to problems such as FISHER: SPOJ

I saw a tutorial on this on TopCoder in the upper intermediate section, for using dijsktra's with another state, but couldn't really understand how to implement it.

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
»
10 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

Expand the graph so each node will be in form (Node,Time). If we are at (Node,Time) that means we have reached node Node in the initial graph at time Time. Then build the new graph. If in the initial graph there is an edge between A and B with weight W just put an edge between (A,t) and (B,t+W) for each t<=1000. Then use Dijkstra's algorithm implemented in O(N*logN) or O((N*1000)*log(N*1000)) in our case.

Edit: By weight I mean the time you need to pass the edge. And the edges of the new graph have weights corresponding to the tolls you need to pay :)

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I'm sorry but could you explain further what you mean when you say "build the new graph". Please share some code too, if it's possible.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it +8 Vote: I do not like it

      Hey :)

      I'm sorry for the poor explanation(it seems it's not explained very well). We will build a new graph(expand the initial graph). Let's talk about the new graph. Each node will be in form (Node in the initial graph, Time). If we are at node (Node, Time) that means we have reached node Node in the initial graph at time Time.

      Here is an example:

      Consider the following case:

      2 30(30 is a random number).

      0 10

      10 0

      0 5

      5 0

      Take a look at node 1:

      If we are in node 1 at time 0 we can reach node 2 at time 10(we need 10 time units to pass the edge between them).

      So put an edge between (1,0) and (2,10) in the new graph with weight 5(we need to pay 5 tolls).

      If we are in node 1 at time 1 we can reach node 2 at time 11.

      So put an edge between(1,1) and (2,11).

      And so on, and so on...

      Then run Dijkstra from Node(1,0). The answer will be the minimum distance(tolls) we need to pay in order to reach (N,0), (N,1), ... or (N,t).

      I need to go out now, maybe later I will provide a code :)

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        The idea looks fantastic. Thanks! But don't you think that building the entire graph itself would be O(t*m), here m is the number of edges, as for every node you shall consider every connected node, at every time t?

        It would work in this case, but I don't think I'll be able to do a problem like SPOJ: ROADS, which has a bigger values for the constraints. Edges = 10000 and Cost = 10000, for each test case and there are 100 test cases.

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
          ← Rev. 2   Vote: I like it +3 Vote: I do not like it

          Why do you think that there are 100 cases? Note that in the statement t!=T. I think they won't be that many and also the time limit is 7s on Cube :)

          → Reply
          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yes, but as programmers, isn't it our duty to think about the worst case scenario :p

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              10 years ago, # ^ |
                Vote: I like it +5 Vote: I do not like it

              And also think about getting AC :P :D

              → Reply
            • »
              »
              »
              »
              »
              »
              »
              10 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              There is no way to understand if it will work except of writing it and then submitting it.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                10 years ago, # ^ |
                  Vote: I like it +3 Vote: I do not like it

                Yes, that's there. I tried it, and it worked :D Thank you so much!

                → Reply
          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
            ← Rev. 3   Vote: I like it 0 Vote: I do not like it

            @P-Nyaglov, can you explain why this doesn't give a TLE? For every test case, you have a E*T *log(E*T) complexity for ROADS. So for every test case you have an O(10^8 log(10^8) ) complexity. If there are even 10 tests, then I'm not sure how Cube is allowing such a complexity. Since parash93's code passes, I am sure it does work, but I can't figure out why.

            EDIT : I just coded it myself too, and it worked. In 0.37s actually. :)

            → Reply