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

関連記事

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分探索(バイナリサーチ)を実装してみました。…

Firebase + Nuxt で認証付きページを作るときに参考にしたいところ
Webアプリケーションのセッション管理にJWT導入を検討する際の考え方 Service Worker によるセッション管理 ユーザー セッションの管理 Nuxt.jsとFirebaseでSPA×SSR×PWA×サーバーレスを実現する CookieとセッションとJWT SSR…

JavaScriptで幅優先探索 (bfs) を実装する
bfsソースコード 前提 bfs関数 テストコード JavaScriptで幅優先探索 (bfs) を実装し簡単な最短経路の探索問題を解いてみました。 AtCoderの問題を参考にしています bfsソースコード 前提 bfs 関数の定義について 引数 table…

JavaScriptでbig-integerでできること
定数 メソッド abs add, plus and bitLength compare compareTo compareAmb divide, over divmod equals, eq greater, gt greaterOrEquals, geq…

ソースコードレビューのポイントをまとめる
ソースコードレビュー時のポイントを各所のブログから集めてまとめました。以下 https://gist.github.com/s-yoshiki/9e446d69cf388703a4711f7e69cba173

最新の投稿

PHP-FPM(php7.4) Apache2.4 on Ubutnu20.04 Webサーバ構築
環境 パッケージの更新 Apache と PHP のインストール Apache のサービスを開始する PHPファイルを作成 参考にしたサイト Ubuntu20.04 に PHP7.4 + Apache2.4 をインストールしてWeb…

PHP-FPM(php7.4) Apache2.4 でWebサーバ構築 on CentOS8
環境 php7.4 のインストール apacheのインストール php-fpmの設定を変更する php-fpm の起動 apacheの起動 確認 おまけ: エラーと解決方法 "System has not been booted with systemd as…

CentOS8 に PHP7.4 インストール
環境 普通にインストールしようとするとphp7.2がインストールされる modularityについて php7.4 インストール CentOS8 に modularity を利用して PHP7.4をインストールした際のメモです。 環境 CentOS8.…

UNIXドメインソケット通信 vs INETドメインソケット通信 php-fpmで動作させる場合の違いについて
結論 ソケット通信について ソケットについて ソケット通信の種類 UNIXドメインソケット通信を行う場合のメリット 参考にしたサイト php-fpm の設定方法で調べた際にIPとポートで設定するパターンとUNIX…

Amplify CLI のインストール
Amplify CLI のインストール Amplify CLI の設定 バックエンド環境作成 Amplify CLI のインストールから設定まで Amplify CLI をインストール 設定 Amplify アプリを初期化 Amplify CLI…

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…

PHP-Parser で PHP5からPHP7で動くコードに自動修正するツールが作る夢をみた
ツールが備える機能条件 PHP-Parser について PHP-Parser の簡単なサンプル ASTオブジェクトの置換・変更 PHP5からPHP7への変更内容を実装する ex1 includeパスを変更する ex2 例外クラスを Exception…

PHP5からPHP7への移行ツールを作るための解析・自動修正ツールを調べる
PHP5からPHP7への下位互換のない機能 使えそうなツールの洗い出し PHPStan phan php7cc php7mar php-to-7-aid Rector php-ast PHP-Parser まとめ 追記 (2021/01/0…

Tags

Dates

© 2021   404 motivation not found