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位

 |