Link to the problem : https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2740
Looks like a shortest path problem, but from possible multiple sources. N is very low so it's sufficient to just use floyd.
First we will create two 2D arrays, dis_brothers and dis_police.
dis_brother will include all shortest paths having the "Police" vertex blocked. ( Not relaxing nodes via it by modifying floyd).
dis_police is the normal Floyd, containing all pairs shortest paths.
After we run floyd 2 times, our solution should be :
Iterating through all exits, and minimizing our answer on dis_brothers[brothers][exit]*160 / dis_police[police][exit].
Getting the answer in O(1), it's also possible to use binary search.
The above approach gets WA. Why is this? It works fine with many test cases. It's based on the following idea, we will not approach the edges the police can wait us on, as he can always wait there, after this we take the minimum speed that makes us sure that we are faster on every possible path.
Link to Code : https://ideone.com/jKFfNb