Submission #19432995


Source Code Expand

Copy
class Heap
  def initialize(&block)
    @a = []
    @f = block
  end

  def push t
    n = @a.size
    @a << t
    
    while n > 0
      i = (n-1) / 2
      @a[n], @a[i] = @a[i], @a[n] if @f[@a[n], @a[i]]
      n = i
    end
  end

  def shift
    n = @a.size - 1
    if n < 1
      @a.pop
    else
      r, @a[0], i = @a[0], @a.pop, 0
      while (j = 2 * i + 1) < n
        j += 1 if j != n - 1 && @f[@a[j+1], @a[j]]
        @a[i], @a[j] = @a[j], @a[i] if @f[@a[j], @a[i]]
        i = j
      end
      r
    end
  end
end

N, M = gets.split.map(&:to_i)
E = Array.new(N) {[]}
M.times do
  f, t, c = gets.split.map(&:to_i)
  E[f] << [t, c]
  E[t] << [f, c]
end

f =-> m {
  c = Array.new(N) {Array.new(m)}
  h = Heap.new {|x,y| x[1] < y[1]}
  h.push [0,0]
  while (i,s = h.shift)
    c[i][s % m] ||= (
      E[i].each {h.push [_1, _2 + s]}if i < N - 1
      s
    )
  end
  c
}
p [f[4][-1][0], f[7][-1][0]].compact.min

Submission Info

Submission Time
Task E - 会場への道
User kuma_rb
Language Ruby (2.7.1)
Score 100
Code Size 973 Byte
Status AC
Exec Time 1258 ms
Memory 21988 KB

Judge Result

Set Name sub1 sub2
Score / Max Score 30 / 30 70 / 70
Status
AC × 15
AC × 26
Set Name Test Cases
sub1 sub1/input_0.txt, sub1/input_1.txt, sub1/input_2.txt, sub1/input_20.txt, sub1/input_21.txt, sub1/input_22.txt, sub1/input_23.txt, sub1/input_24.txt, sub1/input_3.txt, sub1/input_4.txt, sub1/input_5.txt, sub1/input_6.txt, sub1/input_7.txt, sub1/input_8.txt, sub1/input_9.txt
sub2 sub2/input_0.txt, sub2/input_1.txt, sub2/input_10.txt, sub2/input_11.txt, sub2/input_12.txt, sub2/input_13.txt, sub2/input_14.txt, sub2/input_15.txt, sub2/input_16.txt, sub2/input_17.txt, sub2/input_18.txt, sub2/input_19.txt, sub2/input_2.txt, sub2/input_20.txt, sub2/input_21.txt, sub2/input_22.txt, sub2/input_23.txt, sub2/input_24.txt, sub2/input_25.txt, sub2/input_3.txt, sub2/input_4.txt, sub2/input_5.txt, sub2/input_6.txt, sub2/input_7.txt, sub2/input_8.txt, sub2/input_9.txt
Case Name Status Exec Time Memory
sub1/input_0.txt AC 60 ms 14112 KB
sub1/input_1.txt AC 57 ms 14316 KB
sub1/input_2.txt AC 58 ms 14084 KB
sub1/input_20.txt AC 146 ms 14720 KB
sub1/input_21.txt AC 99 ms 14368 KB
sub1/input_22.txt AC 87 ms 14228 KB
sub1/input_23.txt AC 62 ms 14228 KB
sub1/input_24.txt AC 74 ms 14340 KB
sub1/input_3.txt AC 61 ms 14244 KB
sub1/input_4.txt AC 61 ms 14260 KB
sub1/input_5.txt AC 61 ms 14184 KB
sub1/input_6.txt AC 60 ms 14204 KB
sub1/input_7.txt AC 60 ms 14240 KB
sub1/input_8.txt AC 62 ms 14320 KB
sub1/input_9.txt AC 62 ms 14112 KB
sub2/input_0.txt AC 61 ms 14140 KB
sub2/input_1.txt AC 62 ms 14056 KB
sub2/input_10.txt AC 88 ms 14592 KB
sub2/input_11.txt AC 1194 ms 21288 KB
sub2/input_12.txt AC 1193 ms 21412 KB
sub2/input_13.txt AC 96 ms 14568 KB
sub2/input_14.txt AC 1158 ms 21848 KB
sub2/input_15.txt AC 1177 ms 21608 KB
sub2/input_16.txt AC 1258 ms 21892 KB
sub2/input_17.txt AC 1154 ms 21508 KB
sub2/input_18.txt AC 1183 ms 21848 KB
sub2/input_19.txt AC 1198 ms 21988 KB
sub2/input_2.txt AC 57 ms 14236 KB
sub2/input_20.txt AC 148 ms 14832 KB
sub2/input_21.txt AC 98 ms 14244 KB
sub2/input_22.txt AC 93 ms 14232 KB
sub2/input_23.txt AC 62 ms 14096 KB
sub2/input_24.txt AC 74 ms 14256 KB
sub2/input_25.txt AC 85 ms 14848 KB
sub2/input_3.txt AC 61 ms 14040 KB
sub2/input_4.txt AC 61 ms 14292 KB
sub2/input_5.txt AC 59 ms 14164 KB
sub2/input_6.txt AC 62 ms 14180 KB
sub2/input_7.txt AC 60 ms 14184 KB
sub2/input_8.txt AC 62 ms 13984 KB
sub2/input_9.txt AC 62 ms 14440 KB