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

# | User | Rating |
---|---|---|

1 | tourist | 3434 |

2 | OO0OOO00O0OOO0O0…O | 3419 |

3 | Um_nik | 3309 |

4 | fateice | 3306 |

5 | Syloviaely | 3274 |

6 | Petr | 3220 |

7 | dotorya | 3145 |

8 | Radewoosh | 3101 |

9 | mnbvmar | 3096 |

10 | anta | 3053 |

# | User | Contrib. |
---|---|---|

1 | tourist | 178 |

2 | rng_58 | 165 |

3 | Petr | 155 |

3 | csacademy | 155 |

5 | Swistakk | 149 |

5 | lewin | 149 |

7 | Um_nik | 143 |

8 | Errichto | 140 |

9 | Vovuh | 138 |

9 | matthew99 | 138 |

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/25/2018 01:21:29 (d2).

Desktop version, switch to mobile version.

User lists

Name |
---|

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 reopenedIs 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

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

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 .

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

if possible can u please provide your code .

thanks for the help .

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?

Did you just first found the shortest path and then incremented the time as per intersection of the george and luca?