Submission #19432985


Source Code Expand

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

  def push t
    n = @a.size
    @a << tt
    
    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 0
Code Size 974 Byte
Status RE
Exec Time 82 ms
Memory 15264 KB

Judge Result

Set Name sub1 sub2
Score / Max Score 0 / 30 0 / 70
Status
RE × 15
RE × 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 RE 63 ms 14160 KB
sub1/input_1.txt RE 62 ms 14084 KB
sub1/input_2.txt RE 58 ms 14104 KB
sub1/input_20.txt RE 68 ms 14224 KB
sub1/input_21.txt RE 60 ms 14168 KB
sub1/input_22.txt RE 62 ms 14164 KB
sub1/input_23.txt RE 61 ms 14176 KB
sub1/input_24.txt RE 65 ms 14088 KB
sub1/input_3.txt RE 62 ms 14112 KB
sub1/input_4.txt RE 64 ms 14092 KB
sub1/input_5.txt RE 62 ms 14104 KB
sub1/input_6.txt RE 62 ms 14148 KB
sub1/input_7.txt RE 65 ms 14100 KB
sub1/input_8.txt RE 63 ms 14248 KB
sub1/input_9.txt RE 59 ms 14184 KB
sub2/input_0.txt RE 62 ms 14092 KB
sub2/input_1.txt RE 61 ms 14148 KB
sub2/input_10.txt RE 64 ms 14136 KB
sub2/input_11.txt RE 73 ms 15208 KB
sub2/input_12.txt RE 77 ms 15172 KB
sub2/input_13.txt RE 67 ms 14164 KB
sub2/input_14.txt RE 77 ms 15148 KB
sub2/input_15.txt RE 79 ms 15144 KB
sub2/input_16.txt RE 81 ms 15104 KB
sub2/input_17.txt RE 78 ms 14964 KB
sub2/input_18.txt RE 82 ms 15264 KB
sub2/input_19.txt RE 81 ms 14968 KB
sub2/input_2.txt RE 62 ms 14240 KB
sub2/input_20.txt RE 66 ms 14372 KB
sub2/input_21.txt RE 66 ms 14100 KB
sub2/input_22.txt RE 63 ms 14120 KB
sub2/input_23.txt RE 60 ms 14136 KB
sub2/input_24.txt RE 62 ms 13964 KB
sub2/input_25.txt RE 66 ms 14244 KB
sub2/input_3.txt RE 63 ms 14228 KB
sub2/input_4.txt RE 64 ms 14036 KB
sub2/input_5.txt RE 64 ms 13972 KB
sub2/input_6.txt RE 63 ms 14316 KB
sub2/input_7.txt RE 61 ms 14212 KB
sub2/input_8.txt RE 62 ms 14220 KB
sub2/input_9.txt RE 59 ms 14176 KB