ARC083/ABC074 D Restoring Road Network

AtCoder Begginer Contest 083、AtCoder Regular Contest 074 D Restoring Road Network

よくわからなかったので、解説の解説をする。
他の人のコードを見ながら勉強した。
問題がこれ
D - Restoring Road Network
解説がこれ
https://img.atcoder.jp/arc083/editorial.pdf

解説

 i に対して、 \{A_{i,j} \mid j \neq i\} の最小値の長さの辺は必ず存在する。
これで十分では?と思ったけど、そうじゃなさげ。
でも、その時点で最小の重みを持つ辺は確定しそうということが分かる。
それをやってみる。

WF N \times N のリストで、対角成分が 0 でそれ以外の全ての成分が  10^9+1 とする。
ワーシャルフロイドをする。

 \{A_{i,j} \mid i, j\} を最小値から順番にとっていく。

その辺の重みを  a とし、辺を  (s, g) とする。
まず、それを加えるかどうか考えよう。
d でグラフの距離を表すことにする。
全ての  s, g 以外の頂点  i に対して、次の3パターンが考えられる。

1. 任意の i に対して、 WF_{s,i} + WF_{i,g} > a :
こういう辺を追加してもよい。
これが最適である。
まず、これより大きい辺との大小比較をする必要はない。
また、この辺の追加により、最短経路が更新される可能性はない。
このとき、WF_{s,g} = a = WF_{g,s} と更新する。
2. ある i に対して、 WF_{s,i} + WF_{i,g} = a :
同じ距離だから、こういう辺を追加する必要はない。
3. ある i に対して、WF_{s,i} + WF_{i,g} < a :
このような、グラフは存在しない。

解答

import heapq
N = int( input())
A = [ list( map( int, input().split())) for _ in range(N)]
Q = []
for i in range(N-1):
    for j in range(i+1,N):
        heapq.heappush(Q, [A[i][j],i,j])
WF = [ [10**9+1]*N for _ in range(N)]
for i in range(N):
    WF[i][i] = 0
cnt = 0
while Q:
    a, s, g = heapq.heappop(Q)
    addcheck = 1
    for i in range(N): #新しく辺(s,g)を追加できるかどうかを判断する。
        #小さい辺から順番にチェックしているので、より大きい辺との大小比較の必要がない。
        #もう一つ、最短経路が更新される可能性があるが、それは今の辺より真に大きい辺のみなので、問題ない。
        if i == s or i == g:
            continue
        else:
            if WF[s][i] + WF[i][g] == a:
                addcheck = 0
            elif WF[s][i] + WF[i][g] < a:
                 break
    else:
        WF[s][g] = a
        WF[g][s] = a
        if addcheck:
            cnt += a
        continue
    print(-1)
    break
else:
    print( cnt)