Recently I get this task

Based on the system of two-way roads, determine between which cities it is worth building roads so that one can get from any city to any other in less than N km. The distances and construction costs of eligible roads are specified separately. Minimize road construction costs.

I made java graph from two matrix for visualize initial eligible roads, but can't come up with algorithm, I'm not really familiar with graphs)

CodePudding user response：

FOR EVER
    M = 0
    LOOP over every pair of cities 
        If min distance ( Dijkstra algorithm ) between cities > M
           M = min distance
    IF M <= N
        BREAK
    LOOP over eligible roads in order of increasing cost
        IF road would reduce distance between two most distant cities
             BUILD the road

Note that many implementations of Dijkstra will give the minumim distance from a source to every possible destination. This can be used to optimize the loop calculating M