エントリーの編集
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
Numo::NArray でワーシャル–フロイド法の多重ループを記述削減 - Qiita
記事へのコメント0件
- 注目コメント
- 新着コメント
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
Numo::NArray でワーシャル–フロイド法の多重ループを記述削減 - Qiita
多次元配列NArrayの機能を利用すれば、ワーシャル–フロイド法の3重ループのうち内側2つを書かなくてよく... 多次元配列NArrayの機能を利用すれば、ワーシャル–フロイド法の3重ループのうち内側2つを書かなくてよくなる。Rubyレベルの記述が減ることで計算速度も向上する。 (AtCoderのコンテストでスラスラ書けず、NArray不使用で提出してTLEに苦しんだので、きちんと纏めておくことにした。) コード # n頂点m辺の重み付き有向グラフを標準入力から読み込み n, m = gets.split.map!(&:to_i) edges = Array.new(m) { gets.split.map!(&:to_i) } # 隣接行列を作成 d = Numo::Int64.new(n, n).fill(Numo::Int64::MAX >> 1) d.diagonal[true] = 0 edges.each do |i, j, dist| d[i, j] = dist if d[i, j] >