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

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

2020-06-219 min read

目次

  1. 概要
  2. atcoder-abc012-d問題
  3. 実装

概要

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

Recommends
JavaScriptで優先度付きキューを実装する
2021-08-01
javascript
typescript
%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
next_permutationをJSで実装する
2021-07-22
javascript
typescript
%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
10進数から2進数 2進数から10進数への変換 JavaScript
2020-07-12
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
JavaScriptの配列ショートハンド (AtCoder用)
2020-07-05
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
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
JavaScriptによる2分探索(バイナリサーチ) のサンプルコード
2020-05-24
javascript
%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
%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
JavaScriptで幅優先探索 (bfs) を実装する
2020-01-13
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
順列・組み合わせ のサンプルコード JS [permutation] [combina...
2019-06-30
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
JavaScript で bit全探索
2019-06-10
%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
深さ優先探索アルゴリズムを実装 部分和問題を解く
2018-12-25
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
複数キーでソートするサンプルコード JavaScript
2018-11-05
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
[JS]BigIntでMathが使えない件
2022-06-12
javascript
node.js
atcoder
javascriptで累積和を解く
2022-02-27
%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%A0%E3%83%9F%E3%83%B3%E3%82%B0
atcoder
JSで動的計画法を利用して部分和問題を解く
2022-02-20
javascript
typescript
%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
JSで32ビット符号付き整数に対してのビット演算でハマった
2021-02-17
javascript
node.js
%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
New Posts
[JS]Intl.DateTimeFormatで和暦と西暦を変換
2022-08-18
javascript
[NestJS]少し大きな規模のRESTfull APIを構築するディレクトリ構成を考えて...
2022-09-04
nestjs
typescript
%E3%82%A2%E3%83%BC%E3%82%AD%E3%83%86%E3%82%AF%E3%83%81%E3%83%A3
Prisma MySQL でUTC以外の任意のタイムゾーンを利用するのが難しい件
2022-08-08
prisma
typescript
mysql
Prisma TypeScript MySQLなプロジェクトの構築
2022-08-08
prisma
typescript
mysql
Prisma TypeScript SQLiteなプロジェクトの構築
2022-08-06
prisma
typescript
sqlite
[AWS]Lambda vs Fargate. APIを実装する場合に思うこと
2022-07-30
amazon%20aws
amazon%20ecs
%E9%9B%91%E8%AB%87
macOSにzigをインストールしてHello World!する
2022-07-18
zig
mac
[AWS CDK] Cognito の OIDC プロバイダに Auth0 を設定
2022-07-03
auth0
amazon%20aws
aws%20cdk
Amazon S3 でライフサイクルポリシーを設定する
2022-06-19
amazon%20aws
amazon%20s3
AWS Certified Developer Associate に合格した
2022-06-19
amazon%20aws
%E8%B3%87%E6%A0%BC%E8%A9%A6%E9%A8%93
Fisher-Yates shuffleで配列シャッフル [js/ts/php]
2022-06-19
javascript
node.js
typescript
JavaScriptでUTF-16コードを文字列に変換
2022-06-18
javascript
node.js
[JS]乱数でランダムな整数を生成する
2022-06-18
javascript
node.js
[JS]BigIntでMathが使えない件
2022-06-12
javascript
node.js
atcoder
AWS SAPに合格しました
2022-06-11
amazon%20aws
%E8%B3%87%E6%A0%BC%E8%A9%A6%E9%A8%93
Hot posts!
Proxy環境下でcurlを実行する
2019-12-07
linux
curl
OpenCVのMatのタイプ一覧表
2018-11-25
%E7%94%BB%E5%83%8F%E5%87%A6%E7%90%86
opencv
Macでも利用できるDBクライアント MySQL PostgreSQL Oracle など
2019-12-21
linux
%E3%83%87%E3%83%BC%E3%82%BF%E3%83%99%E3%83%BC%E3%82%B9
mysql
TablePlusを使ってみる。シンプルでモダンなSQLクライアントツール
2018-09-30
%E3%83%87%E3%83%BC%E3%82%BF%E3%83%99%E3%83%BC%E3%82%B9
DBクライアントツールはDBeaverをおすすめしたい
2021-03-08
oracle
mysql
sqlite
AWS S3のアクセスキーIDとシークレットアクセスキーの取得 作業用ユーザを作成
2019-06-12
amazon%20aws
linux
amazon%20s3
AtCoderで初めて色がつくまでの話(茶色) レートが中々上がらなかった原因
2018-11-25
%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
%E9%9B%91%E8%AB%87
CentOS8でEPELとPowerToolsリポジトリの有効化
2020-11-30
centos
red%20hat
EPEL
Macでターミナルからポートスキャンを行う方法。
2018-12-09
linux
mac
apple
Python + OpenCVのfillConvexPolyで複雑なポリゴンを描画する
2018-11-27
python
%E7%94%BB%E5%83%8F%E5%87%A6%E7%90%86
opencv
Date
▶︎
2022 年 (39)
▶︎
2021 年 (40)
▶︎
2020 年 (30)
▶︎
2019 年 (90)
▶︎
2018 年 (89)
▶︎
2017 年 (1)
Tags
javascript(98)
amazon%20aws(47)
linux(47)
node.js(38)
%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0(36)
%E7%94%BB%E5%83%8F%E5%87%A6%E7%90%86(30)
html5(29)
typescript(28)
php(24)
centos(24)
python(22)
%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(21)
mysql(19)
mac(19)
canvas(18)
opencv(17)
%E9%9B%91%E8%AB%87(16)
wordpress(15)
atcoder(14)
docker(14)
apache(12)
%E6%A9%9F%E6%A2%B0%E5%AD%A6%E7%BF%92(12)
%E3%83%87%E3%83%BC%E3%82%BF%E3%83%99%E3%83%BC%E3%82%B9(12)
amazon%20s3(12)
red%20hat(12)
ubuntu(11)
github(10)
git(10)
vue.js(10)
%E7%94%BB%E5%83%8F%E5%87%A6%E7%90%86100%E6%9C%AC%E3%83%8E%E3%83%83%E3%82%AF(10)
mariadb(10)
aws%20cdk(9)
css3(8)
%E5%8F%AF%E8%A6%96%E5%8C%96(8)
%E5%B0%8F%E3%83%8D%E3%82%BF(8)
amazon%20lightsail(7)
react(7)
%E3%83%96%E3%83%AD%E3%82%B0(6)
cms(6)
oracle(6)
perl(6)
gitlab(6)
next.js(6)
iam(5)
amazon%20ec2(5)
%E8%B3%87%E6%A0%BC%E8%A9%A6%E9%A8%93(5)
aws%20amplify(5)
curl(4)
webassembly(4)
ssh(4)
Author
s-yoshiki
s-yoshiki
githubzenntwitterqiita
ただの備忘録です。
JavaScript/TypeScript/node.js/React/AWS/OpenCV
※このブログの内容は個人の見解であり、所属する組織等の見解ではありません。