結果

問題 No.1 道のショートカット
ユーザー shi-moshi-mo
提出日時 2016-03-22 00:16:17
言語 Ruby
(3.3.0)
結果
RE  
実行時間 -
コード長 2,412 bytes
コンパイル時間 80 ms
コンパイル使用メモリ 7,296 KB
実行使用メモリ 12,544 KB
最終ジャッジ日時 2024-07-08 04:25:17
合計ジャッジ時間 6,013 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 RE -
testcase_32 RE -
testcase_33 RE -
testcase_34 RE -
testcase_35 RE -
testcase_36 RE -
testcase_37 RE -
testcase_38 RE -
testcase_39 RE -
testcase_40 RE -
testcase_41 RE -
testcase_42 RE -
testcase_43 RE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

#!ruby

require 'scanf'

class ShortcutProblem
  Way = Struct.new('Way', :start, :terminal, :credits, :time)

  def self.load(io)
    num_cities = io.gets.scanf('%d\n')[0]
    credits    = io.gets.scanf('%d\n')[0]
    num_ways   = io.gets.scanf('%d\n')[0]
    ways = load_ways_from(io, num_ways)

    new(num_cities, credits, num_ways, ways)
  end

  def self.load_ways_from(io, num_ways)
    starts    = parse_int_array_from(io.gets)
    terminals = parse_int_array_from(io.gets)
    credits   = parse_int_array_from(io.gets)
    times     = parse_int_array_from(io.gets)

    ways = []
    num_ways.times do |i|
      ways << Way.new(starts[i], terminals[i], credits[i], times[i])
    end
    ways
  end

  def self.parse_int_array_from(line)
    line.chomp.split(/ /).map(&:to_i)
  end

  def initialize(num_cities, credits, num_ways, ways)
    @num_cities = num_cities
    @credits    = credits
    @num_ways   = num_ways

    @way_table  = create_way_table(ways) # elements must be sorted by Way#time
  end
  attr_reader :num_cities, :credits, :num_ways

  NO_SOLUTION = -1
  def solve
    2.upto(num_cities) do |i|
      connect_ways_to(i)
    end

    ways_satisfy_condition = \
      @way_table[1][num_cities].select{|way| way.credits <= credits }

    return NO_SOLUTION if ways_satisfy_condition.empty?
    ways_satisfy_condition.first.time
  end

  def create_way_table(ways)
    table = Array.new(num_cities+1){ Array.new(num_cities+1){ [] } }
    ways.each do |way|
      table_entry = table[way.start][way.terminal]
      table_entry << way
    end
    table
  end

  def connect_ways_to(terminal)
    if 2 == terminal
      sort_table_entry(@way_table[1][2])
      return
    end

    connected_ways = @way_table[1][terminal]
    2.upto(terminal-1) do |pivot|
       ways_before_pivot = @way_table[1][pivot]
       ways_after_pivot  = @way_table[pivot][terminal]

       ways_before_pivot.product(ways_after_pivot) do |way1, way2|
         connected_ways << connect_ways(1, terminal, way1, way2)
       end
    end
    sort_table_entry(connected_ways)
  end

  def sort_table_entry(entry)
    entry.sort_by!{|way| way.time }
  end

  def connect_ways(start, terminal, way1, way2)
    credits = way1.credits + way2.credits
    time    = way1.time    + way2.time

    Way.new(start, terminal, credits, time)
  end
end

def main
  problem = ShortcutProblem.load(STDIN)
  puts problem.solve
end

main
0