結果

問題 No.1 道のショートカット
ユーザー penqenpenqen
提出日時 2020-12-18 23:51:57
言語 Elixir
(1.16.2)
結果
WA  
実行時間 -
コード長 3,721 bytes
コンパイル時間 1,624 ms
コンパイル使用メモリ 65,952 KB
実行使用メモリ 58,304 KB
最終ジャッジ日時 2024-06-10 00:26:37
合計ジャッジ時間 28,147 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 550 ms
54,872 KB
testcase_01 AC 555 ms
54,500 KB
testcase_02 AC 554 ms
55,156 KB
testcase_03 AC 563 ms
54,444 KB
testcase_04 WA -
testcase_05 AC 558 ms
54,120 KB
testcase_06 AC 551 ms
54,788 KB
testcase_07 AC 561 ms
54,640 KB
testcase_08 AC 602 ms
55,268 KB
testcase_09 AC 571 ms
54,824 KB
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 AC 548 ms
54,216 KB
testcase_16 WA -
testcase_17 AC 548 ms
54,932 KB
testcase_18 AC 554 ms
54,724 KB
testcase_19 WA -
testcase_20 WA -
testcase_21 AC 555 ms
54,248 KB
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 AC 584 ms
54,696 KB
testcase_26 WA -
testcase_27 WA -
testcase_28 AC 560 ms
55,792 KB
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 AC 605 ms
54,380 KB
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 AC 541 ms
54,384 KB
testcase_39 WA -
testcase_40 WA -
testcase_41 WA -
testcase_42 AC 562 ms
54,660 KB
testcase_43 AC 553 ms
54,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

defmodule Main do
  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

  defmodule SPF do
    defstruct current: nil,
      destination: nil,
      cost_map: nil,
      max_cost: nil,
      weighted_list: nil

    def next_node({cn, cc, ct}, max, cm) do
      cm[cn]
      |> case do
        nil -> []
        nodes ->  Map.keys(nodes)
      end
      |> Enum.map(fn node ->
        {cost, time} = cm[cn][node]
        {node, cc + cost, ct + time}
      end)
      |> Enum.filter(fn {_node, cost, _time} -> cost <= max end)
      |> Enum.sort(&compaire/2)
    end

    def compaire({_, _, lt}, {_, _, rt}) when lt < rt, do: true
    def compaire({_, lc, lt}, {_, rc, rt}) when lt == rt and lc < rc, do: true
    def compaire(_, _), do: false

    def merge(ll, rl) do
      do_merge(ll, rl)
    end

    defp do_merge([], []), do: []
    defp do_merge([lh | lt], []), do: [lh | do_merge(lt, [])]
    defp do_merge([], [rh | rt]), do: [rh | do_merge([], rt)]
    defp do_merge([lh | lt] = ll, [rh | rt] = rl) do
      if compaire(lh, rh) do
        [lh | do_merge(lt, rl)]
      else
        [rh | do_merge(ll, rt)]
      end
    end
   
    defimpl Enumerable do
      def count(_), do: {:error, __MODULE__}
      def member?(_, _), do: {:error, __MODULE__}
      def slice(_), do: {:error, __MODULE__}

      def reduce(_, {:halt, acc}, _fun), do: {:halted, acc}

      def reduce(%SPF{} = mod, {:suspend, acc}, fun) do
        {:suspended, acc, &reduce(mod, &1, fun)}
      end

      def reduce(%SPF{max_cost: nil}, {:cont, acc}, _fun), do: {:done, acc}
      def reduce(%SPF{destination: nil}, {:cont, acc}, _fun), do: {:done, acc}
      def reduce(%SPF{cost_map: nil}, {:cont, acc}, _fun), do: {:done, acc}
      def reduce(%SPF{weighted_list: []}, {:cont, acc}, _fun), do: {:done, acc}
      def reduce(
        %SPF{
          current: {cn, _, _},
          destination: dst
        },
        {:cont, acc},
        _fun
      ) when cn == dst, do: {:done, acc}

      def reduce(
        %SPF{
          cost_map: cm,
          max_cost: max,
          weighted_list: [h | t]
        } = spf,
        {:cont, acc},
        fun
      ) do
        wl = SPF.merge(t, SPF.next_node(h, max, cm))
        reduce(
          %{
            spf | 
            weighted_list: wl,
            current: h
          },
          fun.(h, acc),
          fun
        )
      end
    end
  end

  def solve(n, c, v, sv, tv, yv, mv) when 2 <= n and n <= 50
    and 1 <= c and c <= 300
    and 1 <= v and v <= 1500
  do
    cost_map = Enum.reduce(0..(v - 1), %{}, fn i, cost_map ->
      s = Enum.at(sv, i)
      t = Enum.at(tv, i)
      y = Enum.at(yv, i)
      m = Enum.at(mv, i)

      cost_map
      |> Map.update(
        s,
        Map.put(%{}, t, {y, m}),
        fn s_map ->
          Map.put(
            s_map,
            t,
            {y, m}
          )
        end
      )
    end)

    %SPF{
      weighted_list: [{1, 0, 0}],
      destination: n,
      cost_map: cost_map,
      max_cost: c
    }
    |> Enum.reduce(nil, fn v, _acc ->
      v
    end)
    |> case do
      {^n, _, time} -> time
      _ -> -1
    end
  end
end
0