Блог пользователя dslearner

spoj george help

Автор dslearner, 11 лет назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
11 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    11 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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

    → Ответить
  • »
    »
    11 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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 .

    → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить
      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        if possible can u please provide your code .

        thanks for the help .

        → Ответить
      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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?

        → Ответить