結果

問題 No.1 道のショートカット
コンテスト
ユーザー penqen
提出日時 2020-12-18 23:51:57
言語 Elixir
(1.18.1)
結果
WA  
実行時間 -
コード長 3,721 bytes
コンパイル時間 1,248 ms
コンパイル使用メモリ 63,148 KB
実行使用メモリ 58,216 KB
最終ジャッジ日時 2024-12-31 05:35:40
合計ジャッジ時間 28,254 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3 WA * 1
other AC * 16 WA * 24
権限があれば一括ダウンロードができます

ソースコード

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