Submission #676838

---

Source Code Expand

let rec tabulate n f = 
  let rec loop acc m =
    if m < n then loop (f m :: acc) (m + 1)
    else List.rev acc in
  loop [] 0

let make_edge n abcs =
  let edge = Array.make n [] in
  List.iter (fun (a, b, c) ->
    edge.(a) <- (b, c) :: edge.(a)) abcs;
  edge

let rec dikjstra ( +. ) q edge d =
  match q with
  | [] -> ()
  | u :: q ->
      let u, q = 
        List.fold_left (fun (u, q') u' ->
          if d.(u) < d.(u') then (u, u' :: q') else (u', u :: q')) (u, []) q in
      List.iter (fun (v, c) ->
        d.(v) <- min d.(v) (d.(u) +. c)) edge.(u);
      dikjstra ( +. ) q edge d

let () =
  let n, m, t = Scanf.scanf "%d %d %d\n" (fun n m t -> n, m, t) in
  let as_ = Array.init n (fun _ -> Scanf.scanf "%d " (fun a -> a)) in
  let abcs = tabulate m (fun _ ->
    Scanf.scanf "%d %d %d\n" (fun a b c -> a - 1, b - 1, c)) in
  let d = Array.make n 1145141919 in
  d.(0) <- 0;
  dikjstra ( + ) (tabulate n (fun i -> i)) (make_edge n abcs) d;
  let d' = Array.make n 1145141919 in
  d'.(0) <- 0;
  dikjstra ( + ) (tabulate n (fun i -> i))
    (make_edge n (List.map (fun (a, b, c) -> (b, a, c)) abcs)) d';
  tabulate n (fun i ->
    as_.(i) * (t - d.(i) - d'.(i)))
  |> List.fold_left max 0
  |> Printf.printf "%d\n"

Submission Info

Judge Result