For a minimax routing problem with precedence conditions and cost functions that allow dependence on the list of tasks, we study the statement for which some of the tasks are allocated as first-priority ones. Other tasks can be started only after the fulfillment of priority tasks. The tasks themselves are connected with visiting megacities and, in particular, individual cities (terms corresponding to works in the field of solving the traveling salesman problem). One needs to find the extremum of arising two-stage problem with a minimax criterion, as well as the optimal compositional solution. In the paper, the optimal algorithm implemented on a PC is substantiated and built; a computational experiment is carried out. Possible applications may be related to some problems of aviation logistics in which it is required to ensure the visit of one vehicle (airplane or helicopter) to a system of aerodromes under a limited fuel reserve at each stage of the flight task; refueling is expected at points of visit (it is also assumed that a set of priority tasks is allocated).