atcoder ABC70 D問題

条件より、ワーシャルフロイドを使えず、DFSの実装、隣接リストの実装が必要な問題だったので、解法をメモる

まず、典型的なワーシャルフロイドについて考える。
ワーシャルフロイドは、グラフがある時に(距離が全て正の値)全ての頂点について、二点間最短距離を簡単に求めるアルゴリズムである。
実装例は下の通り

        int[][] dp = new int[n][n];

        for(int i = 0;i < n;i++){               //入力
            for(int j = 0;j < n;j++){
                int x = sc.nextInt();           //xはiからjまでの距離
                dp[i][j] = x;
            }
        }

        for(int k = 0;k < n;k++){               //ワーシャルフロイド
            for(int i = 0;i < n;i++){
                for(int j = 0;j < n;j++){
                    dp[i][j] = Math.min(dp[i][j], dp[i][k]+dp[k][j]);   //各頂点の二点間最短距離を更新していく
                }
            }
        }

これは実装がすごく簡単だが、一つ難点があって、時間計算量がO(N^3)なので、頂点数が多いとすぐにTLEになってしまう。この問題でも余裕でTLEを起こしてしまうので、違う方法で最短距離を求める方法を考える。
冷静に考えると、この問題の答えは、絶対通らなければならない頂点kというものがあるので、kからの各頂点間最短距離をdfsで求めていけば良いと気づく。時間計算量も、結局全て数えてもN(全頂点数)なので、dfsの時間計算量はO(N)になる。よって、全体の時間計算量は答えなければならない問題数回+O(N)なので、O(Q + N)となり余裕で間に合う。

dfsの実装例は下の通り、

static void dfs(int p,long d){
        depth[p] = d;

        for(int i:graph.get(p).keySet()){               //現在の場所からいける場所のうち、訪れていないところならいく。
            if(!(used[i])){
                used[i] = true;
                dfs(i,  d + graph.get(p).get(i));
            }
        }
        return ;
    }
}

また、今回はグラフを作る時、隣接行列(dp[][]みたいな)を最初は考えたが、それは、明らかに問題条件よりMLEになるのでArrayListの中に、Hashmap<隣接頂点、距離>を入れることで、隣接リストを作った。このリストは、ArrayListのindexを現在の頂点とすることで、各頂点に、Hashmapを入れることで、隣接リストとして機能するようになっている。このリストの注意点としては、まずArrayListにとりあえずなんでもいいので、全てのindexにHashmapを一つ入れること。そうせずに、

graph.get(a).put(b, c);     //getで始点を指定、putで<隣接点、距離>を入れていく

のようにすると、エラーが発生する。また、この最初にHashmapを入れる際も気をつける必要がある。

 HashMap<Integer, Integer> zero = new HashMap<Integer,Integer>();
    for(int i = 0; i <= n;i++){
            zero.put(0, 0);
            graph.add(i, zero);                 //getで始点を指定、putで<隣接点、距離>を入れていく
    }

このようにArrayListの各indexに同じHashmapを入れてしまうと、どのindexに新たにHashmapを追加しても、全てのindexに対してこのHashmapが追加されることになる。よって、下のようにしなければいけない

        for(int i = 0; i <= n;i++){
            HashMap<Integer, Integer> zero = new HashMap<Integer,Integer>();
            zero.put(0, 0);
            graph.add(i, zero);                 //getで始点を指定、putで<隣接点、距離>を入れていく
        }