Link to the problem : https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2740

The approach:

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