結果
問題 | No.1 道のショートカット |
ユーザー | penqen |
提出日時 | 2021-03-08 03:45:22 |
言語 | Elixir (1.16.2) |
結果 |
AC
|
実行時間 | 643 ms / 5,000 ms |
コード長 | 5,516 bytes |
コンパイル時間 | 1,344 ms |
コンパイル使用メモリ | 56,128 KB |
実行使用メモリ | 59,808 KB |
最終ジャッジ日時 | 2023-08-30 01:16:53 |
合計ジャッジ時間 | 31,066 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 614 ms
49,244 KB |
testcase_01 | AC | 619 ms
49,380 KB |
testcase_02 | AC | 610 ms
49,288 KB |
testcase_03 | AC | 622 ms
49,296 KB |
testcase_04 | AC | 611 ms
49,264 KB |
testcase_05 | AC | 615 ms
49,304 KB |
testcase_06 | AC | 604 ms
49,268 KB |
testcase_07 | AC | 607 ms
50,148 KB |
testcase_08 | AC | 622 ms
49,848 KB |
testcase_09 | AC | 608 ms
50,444 KB |
testcase_10 | AC | 607 ms
49,740 KB |
testcase_11 | AC | 606 ms
49,816 KB |
testcase_12 | AC | 610 ms
50,332 KB |
testcase_13 | AC | 597 ms
50,920 KB |
testcase_14 | AC | 597 ms
49,900 KB |
testcase_15 | AC | 616 ms
49,132 KB |
testcase_16 | AC | 615 ms
50,508 KB |
testcase_17 | AC | 622 ms
49,076 KB |
testcase_18 | AC | 632 ms
49,812 KB |
testcase_19 | AC | 619 ms
49,248 KB |
testcase_20 | AC | 614 ms
49,280 KB |
testcase_21 | AC | 609 ms
50,080 KB |
testcase_22 | AC | 602 ms
49,920 KB |
testcase_23 | AC | 604 ms
50,328 KB |
testcase_24 | AC | 605 ms
49,736 KB |
testcase_25 | AC | 616 ms
50,320 KB |
testcase_26 | AC | 605 ms
49,236 KB |
testcase_27 | AC | 606 ms
50,944 KB |
testcase_28 | AC | 603 ms
49,444 KB |
testcase_29 | AC | 619 ms
50,388 KB |
testcase_30 | AC | 614 ms
49,340 KB |
testcase_31 | AC | 608 ms
49,536 KB |
testcase_32 | AC | 625 ms
50,660 KB |
testcase_33 | AC | 643 ms
59,808 KB |
testcase_34 | AC | 624 ms
51,632 KB |
testcase_35 | AC | 607 ms
50,520 KB |
testcase_36 | AC | 621 ms
52,480 KB |
testcase_37 | AC | 629 ms
52,376 KB |
testcase_38 | AC | 611 ms
49,244 KB |
testcase_39 | AC | 613 ms
49,316 KB |
testcase_40 | AC | 621 ms
49,812 KB |
testcase_41 | AC | 624 ms
49,816 KB |
testcase_42 | AC | 619 ms
49,436 KB |
testcase_43 | AC | 627 ms
49,560 KB |
ソースコード
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