## Editorial for LCC '21 Contest 1 S5 - Beanland

**only**when stuck, and

**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.

**Submitting an official solution before solving the problem yourself is a bannable offence.**

Author:

The solution covered in this editorial will use dijkstra's and binary search.

Write a function that takes an argument and returns whether the shortest path between any two nodes is less than after all the edges have been reduced by .

Since , it is sufficient for the function to run dijkstra's times, where each time a new starting node is chosen. If the shortest path from a node to another node is greater than , then the function should return false. If the shortest path between *any* two nodes is less than , then the function should return true.

Now, we binary search for the answer. If the function returns true for a particular value of , then our upper bound decreases. If the function returns false for a particular value of , then our lower bound increases.

**Time Complexity:**

## Comments