提出 #19541152


ソースコード 拡げる

Copy
#!/usr/local/bin/ruby
class PriorityQueue
  def initialize(n,c)
    @n,@c,@cost = n,c,[]
    @blen = (c+1).to_s(2).length+2
    @size = Array.new(@blen+1){|i| 1<<(i-2)}
    @size[0],@size[1],@size[@blen]=:no_size,1,n*c+1
    @bucket = Array.new(@blen+1){[]}
    @bucket[0]=[:not_reached]
    @u = Array.new(@blen+1){|i| (1<<(i-1))-1}
    @u[@blen]=n*c+1
  end
  def insert(v,vcost,idx=@blen)
    idx.downto(0) do |i|
      if @u[i] < vcost
        @bucket[i+1] << v
        @cost[v]=vcost
        return
      end
    end
  end
  def decrease(v,vcost,idx=@blen)
    oldcost = @cost[v]
    idx.downto(1) do |i|
      if @u[i] < oldcost
        @bucket[i+1].delete(v)
        insert(v,newcost,i+1)
        @cost[v]=newcost
        break
      end
    end
  end
  def delete_min
    if @bucket[1].empty?.!
      return @bucket[1].shift
    end
    min_pos,min_vector=nil,nil
    2.upto(@blen) do |i|
      current_bucket = @bucket[i]
      if current_bucket.empty?.!
        min_pos = i
        minv,j = current_bucket[0],0
        current_bucket[1..].each_with_index do |w,k|
          if @cost[minv] > @cost[w]
            minv,j = w,k+1
          end
        end
        current_bucket.delete_at(j)
        min_vector=minv
        break
      end
    end
    @u[0],@u[1]=@cost[min_vector]-1,@cost[min_vector]
    2.upto(min_pos-1) do |i|
      @u[i]=[@u[i-1]+@size[i],@u[min_pos]].min
    end
    while @bucket[min_pos].empty?.!
      w = @bucket[min_pos].shift
      insert(w,@cost[w],min_pos)
    end
    STDERR.puts "#{__method__}: min_vector: #{min_vector}" if $debug
    min_vector
  end
  def cost(v); @cost[v]; end
end

class Jinarashi
  def initialize(h,w,costs,digit=100)
    @h,@w,@priorityqueue,@digit = h,w,nil,digit
    @a = costs || Array.new(h){Array.new(w)}
  end
  def kinbou(idx)
    w,h = idx%@digit,idx/@digit
    arr = []
    arr << @digit*(h-1)+w if 0<h
    arr << @digit*(h+1)+w if h<@h-1
    arr << @digit*h+w-1 if 0<w
    arr << @digit*h+w+1 if w<@w-1
    arr
  end
  def find_corner_by_dijkstra(h,w)
    start_vertex = @digit*h+w
    runset = (0...@h).map{|i|(0...@w).map{|j| @digit*i+j}}.flatten
    res = [[@h-1,0],[@h-1,@w-1],[0,@w-1]].map{|i,j| @digit*i+j}
    res1 = res.dup
    @priorityqueue = PriorityQueue.new(@h*@w,@a.flatten.max)
    @priorityqueue.insert(start_vertex,0)
    while res.size > 0
      point = @priorityqueue.delete_min
      ridx = runset.bsearch_index{_1>=point}
      runset.delete_at(ridx) #point is scanned.
      res.delete(point)
      kinbou(point).each do |idx|
        if runset.bsearch{_1>=idx} == idx
          y,x = idx%@digit,idx/@digit
          newcost = @a[x][y]+@priorityqueue.cost(point)
          if @priorityqueue.cost(idx).nil?
            @priorityqueue.insert(idx,newcost)
          elsif @priorityqueue.cost(idx)>newcost
            @priorityqueue.decrease(idx,newcost)
          end
        end
      end
    end
    res1.map{|idx| @priorityqueue.cost(idx)}.sum+@a[h][w]
  end
  def find_keiro
    distance = @a[-1].sum+@a.map{|b| b[-1]}.sum
    0.upto(@h-1) do |i|
      0.upto(@w-1) do |j|
        distance = [distance,find_corner_by_dijkstra(i,j)].min
      end
    end
    distance
  end
end
h,w = gets.split(" ").map(&:to_i)
arr = Array.new(h){gets.split(" ").map(&:to_i)}
g = Jinarashi.new(h,w,arr)
val = g.find_keiro
puts val
exit 0

提出情報

提出日時
問題 J - 地ならし
ユーザ hytkxd
言語 Ruby (2.7.1)
得点 0
コード長 3442 Byte
結果 TLE
実行時間 2206 ms
メモリ 19732 KB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 0 / 6
結果
AC × 2
AC × 15
TLE × 22
セット名 テストケース
Sample example_01.txt, example_02.txt
All example_01.txt, example_02.txt, subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_01_18.txt, subtask_01_19.txt, subtask_01_20.txt, subtask_01_21.txt, subtask_01_22.txt, subtask_01_23.txt, subtask_01_24.txt, subtask_01_25.txt, subtask_01_26.txt, subtask_01_27.txt, subtask_01_28.txt, subtask_01_29.txt, subtask_01_30.txt, subtask_01_31.txt, subtask_01_32.txt, subtask_01_33.txt, subtask_01_34.txt, subtask_01_35.txt
ケース名 結果 実行時間 メモリ
example_01.txt AC 66 ms 14352 KB
example_02.txt AC 94 ms 14432 KB
subtask_01_01.txt AC 64 ms 14300 KB
subtask_01_02.txt AC 116 ms 14244 KB
subtask_01_03.txt AC 120 ms 15476 KB
subtask_01_04.txt TLE 2206 ms 18852 KB
subtask_01_05.txt TLE 2206 ms 18864 KB
subtask_01_06.txt TLE 2206 ms 19460 KB
subtask_01_07.txt TLE 2206 ms 18788 KB
subtask_01_08.txt AC 290 ms 15344 KB
subtask_01_09.txt TLE 2206 ms 16504 KB
subtask_01_10.txt AC 270 ms 16092 KB
subtask_01_11.txt TLE 2206 ms 18128 KB
subtask_01_12.txt TLE 2206 ms 18636 KB
subtask_01_13.txt TLE 2206 ms 18932 KB
subtask_01_14.txt TLE 2206 ms 19436 KB
subtask_01_15.txt TLE 2206 ms 19732 KB
subtask_01_16.txt TLE 2206 ms 16016 KB
subtask_01_17.txt TLE 2206 ms 16828 KB
subtask_01_18.txt AC 872 ms 15196 KB
subtask_01_19.txt AC 202 ms 15120 KB
subtask_01_20.txt TLE 2206 ms 19320 KB
subtask_01_21.txt TLE 2206 ms 19696 KB
subtask_01_22.txt TLE 2206 ms 19240 KB
subtask_01_23.txt TLE 2206 ms 19476 KB
subtask_01_24.txt AC 83 ms 14804 KB
subtask_01_25.txt AC 65 ms 14168 KB
subtask_01_26.txt TLE 2206 ms 16508 KB
subtask_01_27.txt TLE 2206 ms 17064 KB
subtask_01_28.txt TLE 2206 ms 18656 KB
subtask_01_29.txt TLE 2206 ms 19368 KB
subtask_01_30.txt TLE 2206 ms 19284 KB
subtask_01_31.txt TLE 2206 ms 18448 KB
subtask_01_32.txt AC 1887 ms 15708 KB
subtask_01_33.txt AC 187 ms 14488 KB
subtask_01_34.txt AC 1447 ms 15184 KB
subtask_01_35.txt AC 452 ms 15836 KB