Find the minimal tank capacity to be able to travel from any city to any other There are $n$ cities in the country. The car can go from any city $u$ to city $v$, On this road it spends $w_{u,v} &gt; 0$ fuel. At the same $w_{u,v}$ can differ from $w_{v, u}$. The task is to find the minimal tank capacity to be able to travel from any city to any other (possibly with refuels) in $O(n^2\log n)$.
We first sort all edges according to their costs from small to large. Say the sorted edges are $e_1,e_2,\ldots,e_{n(n-1)}$, and the corresponding costs are $w_1\le w_2\le\cdots\le w_{n(n-1)}$. Then we find the minimal $i$ such that the graph is strongly connected only with the edges $e_1,\ldots,e_i$. Now $w_i$ is the minimal tank capacity we want.

Sorting costs $O(n^2\log n)$ time. To find the minimal $i$, we can use the bisection method. We first test whether the graph is strongly connected with the edges $e_1,\ldots,e_{n(n-1)/2}$. If yes, we then test the connectivity with the edges $e_1,\ldots,e_{\lceil n(n-1)/4\rceil}$, otherwise we test the connectivity with the edges $e_1,\ldots,e_{\lceil3n(n-1)/4\rceil}$, and so on. The running time to find the minimal $i$ is also $O(n^2\log n)$. So the total running time of this algorithm is $O(n^2\log n)$.