サンプルを使ってワーシャルフロイドした結果が、サンプルと一致していなければ答えは -1 となる。 そうでない場合は存在する道の和を出力しないといけないが、それは i から j に道が引かれているとき == min( d[ i ][ k ] + d[ k ][ j ] ) > d[ i ][ j ] …

ワーシャルフロイド法を二回使うらしい。思いつけるのか？ 解説読んで5分くらい考えて解説が正しいことを理解した。 python だと from scipy.sparse import csr_matrix from scipy.sparse.csgraph import floyd_warshall で簡単にワーシャルフロイド法ができ…

ワーシャルフロイド法で解く問題 街の通り方は順列で全探索した 計算量は最大(200**3 + 8!) くらいで pypy3 で 330ms def warshall_floyd(d): #d[i][j]: iからjへの最短距離 for k in range(n): for i in range(n): for j in range(n): d[i][j] = min(d[i][j…

ほかっておいた蟻本の2-5章を進め始めた 蟻本がC+で書かれていても、先人の方々が python のコードをまとめてくださっているので独学でもなんとか耐えている 神サイト 蟻本 初級編 python カテゴリーの記事一覧 - じゅっぴーダイアリー今回はワーシャルフロ…