結果
| 問題 |
No.1 道のショートカット
|
| コンテスト | |
| ユーザー |
 penqen
|
| 提出日時 | 2021-03-08 03:45:22 |
| 言語 | Elixir (1.18.1) |
| 結果 |
AC
|
| 実行時間 | 594 ms / 5,000 ms |
| コード長 | 5,516 bytes |
| コンパイル時間 | 1,204 ms |
| コンパイル使用メモリ | 65,320 KB |
| 実行使用メモリ | 65,360 KB |
| 最終ジャッジ日時 | 2024-12-31 05:38:34 |
| 合計ジャッジ時間 | 27,572 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 40 |
コンパイルメッセージ
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
ソースコード
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