We designed this problem for the Electronic Contest, but we had too many problems there so we used it in the finals instead.
To solve the problem, first find the time of the shortest path from each unit to each base. Then starting from some upper and lower bound, one can find the minimal required time to conquer all the bases with a binary search. Each iteration is a check if units can be matched to bases that are closer than the given time (maximum matching in a bipartite graph).