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

2020-06-21

概要

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を出力する。

解説

AtCoder Beginner Contest 012 解説 from AtCoder Inc.

実装

"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'));