Hatena::Grouptopcoder

tochukasoの日記

2014-07-12

ABC B12

| 00:38

今回はテスト時間内の初の4完(前に400点はあったけど、満点が401点の時だったから、これが初の全完)

A,B,Cは単純なシミュレーション

D問題

 ・V個の頂点、E個の辺がある。

 ・任意の頂点からの最長距離が最短となる頂点を求める。

 ・競技プログラミングコンテストで初めての

  ダイクストラ法を使って、O(V^3)で解いた。

  半年前なら絶対に解けなかっただろうから、これが解けたのは感慨深い。

  Rは伸びないけど、きっと力はついてると思う。

    void solve() throws Throwable {
        startTime = System.currentTimeMillis();
        
        int N = readInt();
        int M = readInt();
        int[][] roads =  readIntMatrix(M);
        
        Map<Integer, List<Integer[]>> map = new HashMap<Integer, List<Integer[]>>();
        for (int i = 1; i <= N; i++) {
            map.put(i, new ArrayList<Integer[]>());
        }
        
        for (int i = 0; i < M; i++) {
            {
                List<Integer[]> list = map.get(roads[i][0]);
                int[] arr = {roads[i][1], roads[i][2]};
                list.add(convIntArray(arr));
            }
            {
                List<Integer[]> list = map.get(roads[i][1]);
                int[] arr = {roads[i][0], roads[i][2]};
                list.add(convIntArray(arr));
            }
        }
        
        int min = Integer.MAX_VALUE;
        
        for (int i = 1; i <= N; i++) {
            
            int[] dp = new int[N + 1];
            boolean[] used = new boolean[N+1];
            Arrays.fill(dp, Integer.MAX_VALUE - 100);
            dp[i] = 0;
            for (int z = 1; z <= N; z++) {
               
                int f = -1;
                int time = Integer.MAX_VALUE;
                for (int j = 1; j <= N; j++) {
                    if(!used[j] && time > dp[j]) {
                        time = dp[j];
                        f = j;
                    }
                }
                used[f] = true;
                
                List<Integer[]> list = map.get(f);
                for (Integer[] integers : list) {
                    int to = integers[0];
                    int t = integers[1];
                    dp[to] = Math.min(dp[to], dp[f] + t);
                }
            } 
            
            int max = 0;
            for (int j = 1; j <= N; j++) {
                max = Math.max(max, dp[j]);
            }
            
            min = Math.min(min, max);
        }
        
        pw.println(min);
    }    

162位

2014-06-09

アルゴリズムのお勉強

| 12:15

wikipediaとかを見たほうが分かりやすい説明が書いてあるけれど、

自分が勉強したってことを忘れないために書いとく。

★ダイクストラ法

 最短経路を求める際に使用する。

 ただし、負の経路が含まれる場合に無限ループする。

 (更新済みの頂点に対して移動しなくすれば動くと思われる。)

 まずは全ての頂点のコストをINFに設定する。

 始点sと接弦している点iのコストを辺siのコストで更新する。

 以下の部分をループする。(実装上は始点からの処理もこのループ処理に含めてよい。

 1.更新済みの頂点の中からコストが小さいもの(頂点k)を選択する。

 2.接弦している頂点のコストを更新する。

  (更新対象のコスト < 頂点K + 辺Kiのコスト)の場合更新しない。

★クラスカル法

 最小全域木を求める際に使用する。

 最小全域木・全ての頂点を接続(点Aから点Nまで何かしらの経路で移動出来る様に)した際に、

       各辺のコストの総和が最小のグラフ

 

 まずはUnionFind木(頂点がある集合に属しているかを管理するためのツリー。蟻本84P)を用意する。

 UnionFindのサイズは、頂点の数分とする。

 以下の処理をループする。

 1.各辺をコストが小さい順に選択する。

 2.選択した辺の頂点A,BがUnionFindの同一グループに所属しているか調べる。

 3.同一グループに所属している場合、1の処理に戻る。(その辺が閉路となるため。)

   同一グループに所属していない場合、今回選択した辺を最小全域木の辺として採用する。

   頂点Aと頂点Bを同一のグループとして扱う。(Uf#unite)