結果

問題 No.1 道のショートカット
ユーザー penqenpenqen
提出日時 2021-03-08 03:45:22
言語 Elixir
(1.16.2)
結果
AC  
実行時間 624 ms / 5,000 ms
コード長 5,516 bytes
コンパイル時間 1,367 ms
コンパイル使用メモリ 64,316 KB
実行使用メモリ 64,700 KB
最終ジャッジ日時 2024-06-10 00:28:53
合計ジャッジ時間 27,702 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 542 ms
55,432 KB
testcase_01 AC 536 ms
55,100 KB
testcase_02 AC 548 ms
53,948 KB
testcase_03 AC 550 ms
54,492 KB
testcase_04 AC 543 ms
54,128 KB
testcase_05 AC 624 ms
54,632 KB
testcase_06 AC 559 ms
54,788 KB
testcase_07 AC 550 ms
54,220 KB
testcase_08 AC 590 ms
54,760 KB
testcase_09 AC 595 ms
54,528 KB
testcase_10 AC 567 ms
54,768 KB
testcase_11 AC 556 ms
55,124 KB
testcase_12 AC 594 ms
56,064 KB
testcase_13 AC 605 ms
54,888 KB
testcase_14 AC 580 ms
54,196 KB
testcase_15 AC 575 ms
54,136 KB
testcase_16 AC 591 ms
55,988 KB
testcase_17 AC 583 ms
54,328 KB
testcase_18 AC 562 ms
54,632 KB
testcase_19 AC 566 ms
54,744 KB
testcase_20 AC 585 ms
54,252 KB
testcase_21 AC 559 ms
54,496 KB
testcase_22 AC 554 ms
54,980 KB
testcase_23 AC 593 ms
55,532 KB
testcase_24 AC 583 ms
55,492 KB
testcase_25 AC 565 ms
54,352 KB
testcase_26 AC 563 ms
54,336 KB
testcase_27 AC 555 ms
55,176 KB
testcase_28 AC 548 ms
53,988 KB
testcase_29 AC 602 ms
55,844 KB
testcase_30 AC 535 ms
54,220 KB
testcase_31 AC 543 ms
55,360 KB
testcase_32 AC 554 ms
56,236 KB
testcase_33 AC 620 ms
64,700 KB
testcase_34 AC 597 ms
57,204 KB
testcase_35 AC 546 ms
54,380 KB
testcase_36 AC 564 ms
56,344 KB
testcase_37 AC 559 ms
57,584 KB
testcase_38 AC 572 ms
54,460 KB
testcase_39 AC 555 ms
54,216 KB
testcase_40 AC 557 ms
54,844 KB
testcase_41 AC 539 ms
54,608 KB
testcase_42 AC 546 ms
54,104 KB
testcase_43 AC 555 ms
54,392 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
    warning: missing parentheses for expression following "do:" keyword. Parentheses are required to solve ambiguity inside keywords.

    This error happens when you have function calls without parentheses inside keywords. For example:

        function(arg, one: nested_call a, b, c)
        function(arg, one: if expr, do: :this, else: :that)

    In the examples above, we don't know if the arguments "b" and "c" apply to the function "function" or "nested_call". Or if the keywords "do" and "else" apply to the function "function" or "if". You can solve this by explicitly adding parentheses:

        function(arg, one: if(expr, do: :this, else: :that))
        function(arg, one: nested_call(a, b, c))

    Ambiguity found at:
    │
 50 │       do: if comparator.(elem(left, 1), elem(right, 1)),
    │       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    │
    └─ Main.exs:50

ソースコード

diff # 

defmodule Main do
  defmodule Matrix do
    def put(map, keys, value), do: do_map_put(value, keys, map)
  
    defp do_map_put(value, keys, map)
    defp do_map_put(value, [], _), do: value
    defp do_map_put(value, [key | tail], nil), do: Map.put(%{}, key, do_map_put(value, tail, Map.get(%{}, key)))
    defp do_map_put(value, [key | tail], map), do: Map.put(map, key, do_map_put(value, tail, Map.get(map, key)))
  
    def get(map, key_or_keys)
    def get(nil, _key), do: nil
    def get(map, [key | []]), do: Map.get(map, key)
    def get(map, [key | tail]), do: get(Map.get(map, key), tail)
    def get(map, key), do: Map.get(map, key)
  end

  defmodule Heap do
    defstruct data: nil, comparator: nil
  
    def new(comparator), do: %__MODULE__{comparator: comparator}
  
    def empty?(%__MODULE__{data: nil}), do: true
    def empty?(%__MODULE__{}), do: false 
  
    def size(%__MODULE__{data: nil}), do: 0
    def size(%__MODULE__{data: {size, _value, _left, _right}}), do: size

    def top(%__MODULE__{data: nil}), do: nil
    def top(%__MODULE__{data: {_size, value, _left, _right}}), do: value
  
    def pop(%__MODULE__{data: data, comparator: comp} = heap) do
      %{ heap | data: do_pop(comp, data)}
    end
  
    defp do_pop(_comparator, nil), do: nil
    defp do_pop(comparator, {size, _v0, left, right}) do
      with nil <- swap_on_pop(comparator, left, right) do
        nil
      else
        {v1, left, right} ->
          {size - 1, v1, do_pop(comparator, left), right}
      end
    end
  
    defp swap_on_pop(comparator, left, right)
    defp swap_on_pop(_comparator, nil, nil),   do: nil
    defp swap_on_pop(_comparator, left, nil),  do: {elem(left, 1), left, nil}
    defp swap_on_pop(_comparator, nil, right), do: {elem(right, 1), right, nil}
    defp swap_on_pop(comparator, left, right),
      do: if comparator.(elem(left, 1), elem(right, 1)),
        do:   {elem(left, 1), left, right},
        else: {elem(right,1), right, left}

    def push(%__MODULE__{data: data, comparator: comp} = heap, value) do
      %{
        heap |
        data: do_push(value, comp, data)
      }
    end
  
    defp do_push(value, comparator, data \\ nil)
    defp do_push(v0, _comparator, nil), do: {1, v0, nil, nil}
    defp do_push(v0, comparator, {size, v1, nil, nil}) do
      {v0, v1} = swap_on_push(v0, v1, comparator) 
      {size + 1, v0, do_push(v1, comparator), nil}
    end
    defp do_push(v0, comparator, {size, v1, left, nil}) do
      {v0, v1} = swap_on_push(v0, v1, comparator) 
      {size + 1, v0, left, do_push(v1, comparator)}
    end
    defp do_push(v0, comparator, {size, v1, nil, right}) do
      {v0, v1} = swap_on_push(v0, v1, comparator) 
      {size + 1, v0, do_push(v1, comparator), right}
    end
    defp do_push(v0, comparator, {size, v1, {ls, _, _, _} = left, {rs, _, _, _} = right}) do
      {v0, v1} = swap_on_push(v0, v1, comparator) 
      if rs < ls do
        {size + 1, v0, left, do_push(v1, comparator, right)}
      else
        {size + 1, v0, do_push(v1, comparator, left), right}
      end
    end
  
    defp swap_on_push(v0, v1, comparator) do
      if comparator.(v0, v1) do
        {v0, v1}
      else
        {v1, v0}
      end
    end
  end

  def main do
    n = IO.read(:line) |> String.trim() |> String.to_integer()
    c = IO.read(:line) |> String.trim() |> String.to_integer()
    v = IO.read(:line) |> String.trim() |> String.to_integer()
    sn = IO.read(:line) |> String.trim() |> String.split(" ") |> Enum.map(&String.to_integer/1)
    tn = IO.read(:line) |> String.trim() |> String.split(" ") |> Enum.map(&String.to_integer/1)
    yn = IO.read(:line) |> String.trim() |> String.split(" ") |> Enum.map(&String.to_integer/1)
    mn = IO.read(:line) |> String.trim() |> String.split(" ") |> Enum.map(&String.to_integer/1)
    solve(n, c, v, sn, tn, yn, mn) |> IO.puts()
  end

  def solve(n, c, _v, sv, tv, yv, mv) do
    fn {_ln, ly, lm}, {_rn, ry, rm} ->
      lm < rm || (lm == rm && ly < ry)
    end
    |> Heap.new()
    |> Heap.push({1, 0, 0})
    |> do_solve(n, c, build_cost_map(sv, tv, yv, mv))
  end

  defp do_solve(heap, goal, max_cost, cost_map) do
    with false <- Heap.empty?(heap),
      {g, y, t} when g == goal and y <= max_cost <- Heap.top(heap) do
        t
    else
      true ->
        -1
      nil ->
        -1
      {current_node, current_yen, current_time} ->
        heap = Heap.pop(heap)

        cost_map
        |> Map.get(current_node)
        |> case do
          nil ->
            heap
          map ->
            map
            |> Map.keys()
            |> Enum.reduce(heap, fn next_node, heap ->
              Matrix.get(cost_map, [current_node, next_node])
              |> Enum.reduce(heap, fn {yen, time}, heap ->
                Heap.push(heap, {next_node, current_yen + yen, current_time + time})
              end)
            end)
        end
        |> do_solve(goal, max_cost, cost_map)
    end
  end

  def build_cost_map(sv, tv, yv, mv), do: do_build_cost_map(sv, tv, yv, mv)
  defp do_build_cost_map(sv, tv, yv, mv, map \\ %{})
  defp do_build_cost_map([], [], [], [], map), do: map
  defp do_build_cost_map([s | sv], [t | tv], [y | yv], [m | mv], map) do
    if s < t do
      with nil <- Matrix.get(map, [s, t]) do
        do_build_cost_map(sv, tv, yv, mv, Matrix.put(map, [s, t], [{y, m}]))
      else
        list ->
          do_build_cost_map(sv, tv, yv, mv, Matrix.put(map, [s, t], [{y, m} | list]))
      end
    else
      do_build_cost_map(sv, tv, yv, mv)
    end
  end
end
0