#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/mixed-practice-shortest-paths/greg-and-graph-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/mixed-practice-shortest-paths/greg-and-graph-implementation

Repovive

Codeforces 295B Greg and Graph - Implementation - Mixed Practice - Shortest Paths | Graph Theory | Repovive

Repovive.

Graph Theory37 sections · 1633 units81h total

Open in Course

Codeforces 295B Greg and Graph - Implementation

(Reverse Floyd-Warshall)

Add nodes in reverse deletion order:

order = reverse of deletion order
dist = 2D array, all infinity
added = array, all false
answers = empty list

for k in order:
    added[k] = true
    dist[k][k] = 0
    for i where added[i]:
        dist[i][k] = adj[i][k]
        dist[k][i] = adj[k][i]

    for i where added[i]:
        for j where added[j]:
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    sum = 0
    for i where added[i]:
        for j where added[j]:
            sum = sum + dist[i][j]
    answers.append(sum)

print reverse of answers