ソースコード 拡げる

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

```

#### 提出情報

提出日時 2021-01-21 00:44:55+0900 J - 地ならし hytkxd Ruby (2.7.1) 0 3442 Byte TLE 2206 ms 19732 KB

#### ジャッジ結果

セット名 Sample All

 AC × 2
 AC × 15 TLE × 22
セット名 テストケース
Sample example_01.txt, example_02.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