AtCoder Begginer Contest 083、AtCoder Regular Contest 074 D Restoring Road Network
よくわからなかったので、解説の解説をする。
他の人のコードを見ながら勉強した。
問題がこれ
D - Restoring Road Network。
解説がこれ
https://img.atcoder.jp/arc083/editorial.pdf。
解説
各 に対して、 の最小値の長さの辺は必ず存在する。
これで十分では?と思ったけど、そうじゃなさげ。
でも、その時点で最小の重みを持つ辺は確定しそうということが分かる。
それをやってみる。
を のリストで、対角成分が でそれ以外の全ての成分が とする。
ワーシャルフロイドをする。
を最小値から順番にとっていく。
その辺の重みを とし、辺を とする。
まず、それを加えるかどうか考えよう。
でグラフの距離を表すことにする。
全ての 以外の頂点 に対して、次の3パターンが考えられる。
1. 任意の に対して、 :
こういう辺を追加してもよい。
これが最適である。
まず、これより大きい辺との大小比較をする必要はない。
また、この辺の追加により、最短経路が更新される可能性はない。
このとき、 と更新する。
2. ある に対して、 :
同じ距離だから、こういう辺を追加する必要はない。
3. ある に対して、 :
このような、グラフは存在しない。
解答
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)