dslearner's blog

spoj george help

By dslearner, 11 years ago, In English

ques link

plz help me with this one . not able to code it . actually having troubles with marking the time for minister .

any help or code will be much appreciated .

thanks

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Okay I came up with a solution, (Assuming if Luka arrives at a blocked street, he can wait till it's reopened, the statement is not clear about this but I believe this is the case).

You will run normal dijkstra on the graph, but taking into consideration that, when moving from a vertex to another vertex using an edge, you need to make sure that GEORGE is not using it at this exact time, if he is using it then the cost of moving along this road will be road cost + time needed until the road is reopened

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

    Is your problem just marking the time for the minister? If this is case then you can simply iterate over all the path given every time since the constraints are small, but if you are looking for an efficient implementation, then here is what to do

    1. Scan the path
    2. Scan all edges
    3. Now for every consecutive vertices in the path add their costs and accumulate the results (You can get the edge costs using a map or just use an adjacency matrix)

    Now you know for every edge in George's path the time he will arrive at it and the time he will be leaving it

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

    if the road is blocked there is a possibility that he takes another route if waiting time + road travelling time is greater than some other path. than he will take the other path .

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

      Yes I know, normal dijkstra should work correctly for this problem

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

        if possible can u please provide your code .

        thanks for the help .

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

        I have applied Dijkstra's algorithm and the solution is accepted. But, I don't think my solution gives the least amount of time to reach the destination. As dslearner suggested there might exist some other path through which we can reach the destination in lesser time by reducing the delays. Can you please clarify?

        → Reply