結果

問題 No.1 道のショートカット
コンテスト
ユーザー shi-mo
提出日時 2016-03-22 00:48:39
言語 Ruby
(3.4.1)
結果
RE  
実行時間 -
コード長 2,245 bytes
コンパイル時間 169 ms
コンパイル使用メモリ 7,552 KB
実行使用メモリ 12,544 KB
最終ジャッジ日時 2024-07-08 04:25:23
合計ジャッジ時間 4,969 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 4
other RE * 40
権限があれば一括ダウンロードができます
コンパイルメッセージ
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)
  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.map{|way| way.time }.sort!.first
  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
      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
  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