JavaScriptでワーシャルフロイド法を実装

2020-06-21
javascript%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0
    

目次

概要

AtCoder ABC012 の D問題でワーシャルフロイド法が利用できる問題が出てきたので、 JavaScriptで実装しました。

AtCoder ABC012 D問題

D - バスと避けられない運命

問題内容を簡潔に表現すると

ルール

N M
a1 b1 t1
a2 b2 t2
:
aM bM tM
  • N ( 2 <= N <= 300 )
  • M ( N-1 <= M <= 44850 )
  • ai,bi ( 1 <= ai,bi <= N )
  • ti (1 <= ti <= 1000)
  • ai != bi

ai と bi は座標を表しており、ti は ai と bi 間の距離である。

求めたいものは ある一つの選択した座標から自身以外の他の全ての座標までの距離を求めその中から最長の物を選ぶ。 この最長の距離がM個の座標の中で最も小さくなるようなものを答えとして出力する。

サンプル

入力値が次の場合を考える。

3 2
1 2 10
2 3 10

1から2までの距離は10、1から3までの距離は20、2から3までの距離は10となる。

よって2を選択したときに最大の距離が10となるため、10を出力する。

解説

実装

"use strict"
function main(arg) {
    let tmp = arg.trim().split("\n").map(e => e.split(" ").map(Number))
    const V = tmp[0][0]
    const E = tmp[0][1]
    tmp.shift()
    let data = tmp

    const MAX = 10e9;
    let graph = Array.from(new Array(V), () => new Array(V).fill(MAX));

    for (let i = 0; i < data.length; i++) {
        let a = data[i][0] - 1
        let b = data[i][1] - 1
        let t = data[i][2]
        graph[a][b] = t
        graph[b][a] = t
    }
    
    // ワーシャルフロイド
    for (let k = 0; k < V; k++) {
        for (let i = 0; i < V; i++) {
            for (let j = 0; j < V; j++) {
                graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j])
                if (i === j) {
                    graph[i][j] = 0
                }
            }
        }
    }

    // console.log(JSON.stringify(graph,null,' '));

    let ans = 10e9;
    let max_temp = 0;

    for (let i = 0; i < V; i++) {
        for (let j = 0; j < V; j++) {
            if (max_temp < graph[i][j]) {
                max_temp = graph[i][j];
            }
        }
        if (ans > max_temp) {
            ans = max_temp;
        }
        max_temp = 0;
    }

    console.log(ans);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

入力値が

3 2
1 2 10
2 3 10

だった場合、 ワーシャルフロイドで計算された変数graphは次のようになる。

[[20,10,20],[10,20,10],[20,10,20]]

この2次元配列の行の中の最大値が一番小さいものを求めればOK

    
s-yoshiki
s-yoshiki
githubtwitterqiita
Web作ってますが、インタラクティブなプログラミングも好きです。
JavaScript / Vue / node.js / PHP / AWS / OpenCV

関連記事

JSで32ビット符号付き整数に対してのビット演算でハマった
具体例 参考にしたサイト JSでサブネットマスクの計算を行おうとしたとき、ビット演算でハマりました。その時のメモです。 JSでサブネットマスクの計算 JSでビット演算子を利用する場合 3…

JSでIPアドレスがサブネットマスクで指定した範囲内にあるか判定する
IPアドレスが指定した範囲内にあるかどうか判定 参考にしたサイト JSでIPアドレス(IPv4)が指定したサブネットの範囲に含まれるか判定するロジックを作った時の記録です。 IPアドレスが指定した範囲内にあるかどうか判定 処理としては、IP…

プログラムの数値計算で発生する誤差の種類 丸め誤差・打ち切り誤差・桁落ち
はじめに 誤差の種類 丸め誤差 打ち切り誤差 桁落ち 情報落ち 桁溢れ誤差 参考にしたサイト コンピュータで出てくる誤差はいくつかありますが、 それらをコードに落として整理しました。 はじめに 例えば の計算の答えは 0.6666666666…

JSでサブネットマスクの計算
JSによるサブネットマスク関連の計算 IPv4アドレス文字列をNumber型に変換する CIDR と サブネットの相互変換 ネットワークアドレス と ブロードキャストアドレス クラス 改めて計算方法を整理する 参考にさせていただいたサイト JSでIPv…

AWS Amplify に Next.js (SSG) で作ったアプリをデプロイする
はじめに 操作 Next.js (React) アプリの作成、Gitへのプッシュ AWS Amplifyでプロジェクト作成 参考にしたサイト この記事では、React / Next.js アプリケーションを作成し、AWS Amplify…

Typescriptに入門した
初期作業 とりあえずHello World 初期作業 typescript環境を作っていきます。 とりあえずHello World まず、次のサンプルコードを作成します。 typescriptファイルをビルドします。

Vue/Nuxt.js 触ってた人が Next.js に入門する
はじめに 実施環境 学習ガイド Create a Next.js App Navigate Between Pages ページの作成 リンク Assets, Metadata, and CSS Assets メタデータ CSS…

10進数から2進数 2進数から10進数への変換 JavaScript
10進数から2進数 2進数から10進数 テスト 10進数から2進数、2進数から10進数への変換を行うJavaScriptのコードの紹介。 JSの場合、10進数から2進数への変換はメソッド。2進数から1…

JavaScriptの配列ショートハンド (AtCoder用)

JavaScriptによる2分探索(バイナリサーチ) のサンプルコード
2分探索について ソース 参考 JavaScriptで2分探索(バイナリサーチ)を実装してみました。…

最新の投稿

フェールセーフやフェールソフト・フールプルーフ 障害対策用語のまとめ

JSで32ビット符号付き整数に対してのビット演算でハマった
具体例 参考にしたサイト JSでサブネットマスクの計算を行おうとしたとき、ビット演算でハマりました。その時のメモです。 JSでサブネットマスクの計算 JSでビット演算子を利用する場合 3…

Gitにプロキシを設定する
プロキシを設定する 確認 Gitでプロキシを通しておくメモです。 プロキシを設定する 以下のコマンドでproxyを通します。 ※ がプロキシのURL…

JSでIPアドレスがサブネットマスクで指定した範囲内にあるか判定する
IPアドレスが指定した範囲内にあるかどうか判定 参考にしたサイト JSでIPアドレス(IPv4)が指定したサブネットの範囲に含まれるか判定するロジックを作った時の記録です。 IPアドレスが指定した範囲内にあるかどうか判定 処理としては、IP…

プログラムの数値計算で発生する誤差の種類 丸め誤差・打ち切り誤差・桁落ち
はじめに 誤差の種類 丸め誤差 打ち切り誤差 桁落ち 情報落ち 桁溢れ誤差 参考にしたサイト コンピュータで出てくる誤差はいくつかありますが、 それらをコードに落として整理しました。 はじめに 例えば の計算の答えは 0.6666666666…

JSでサブネットマスクの計算
JSによるサブネットマスク関連の計算 IPv4アドレス文字列をNumber型に変換する CIDR と サブネットの相互変換 ネットワークアドレス と ブロードキャストアドレス クラス 改めて計算方法を整理する 参考にさせていただいたサイト JSでIPv…

Homebrew で php7.4 + Xdebug をインストール
php7.4のインストール Xdebugのインストール php.ini に追記 参考にさせていただいたサイト phpunitのカバレッジを算出を行うためにMacにHomebrewでphp7.4をインストールしようとした際の記録です。 php7.…

CentOS で スマートにプロキシを設定する
コマンドライン上で通す よりスマートに設定する 設定ファイルに記述 CentOSでプロキシを通す設定のメモです。 プロキシ環境で yum/dnf でリポジトリを更新する場合や、curl/wget…

MySQL8.0 で利用できるパラメータを表示する方法
オプションの表示 mysql8.0でmy.cnfなどで利用できるパラメータ一覧を出す方法。 オプションの表示 オプションの表示は次のコマンドで実施できます mysqld — The MySQL Server 【MySQLパラメーター比較資料】MySQL 5.…

CentOS に MySQL8.0をインストールする
はじめに 環境 起動 MySQLインストール my.cnf の設定 プロセス立ち上げ エラー The designated data directory /var/lib/mysql/ is unusable. You can remove all files…

Tags

Dates

© 2021   404 motivation not found