Submission #3228121

---

Source Code Expand

module IntMap = Map.Make (struct
  type t = int
  let compare = compare
end)

let rec lower_bound l r p =
  if r <= 1 + l
  then r
  else let m = (l + r) / 2 in
       if p m
       then lower_bound l m p
       else lower_bound m r p

let () = Scanf.scanf "%d %d %d %d\n" @@ fun n m r t ->
  let es = Array.make n [] in
  for i = 0 to m - 1 do
    Scanf.scanf "%d %d %d\n" @@ fun a b c ->
      es.(a - 1) <- (b - 1, c) :: es.(a - 1);
      es.(b - 1) <- (a - 1, c) :: es.(b - 1)
  done;
  let d = Array.make_matrix n n max_int in
  for s = 0 to n - 1 do
    d.(s).(s) <- 0;
    let rec dijkstra q =
      match IntMap.min_binding q with
      | exception Not_found -> ()
      | (w, us) -> dijkstra @@ List.fold_left (fun q u ->
          if d.(s).(u) < w then q
          else List.fold_left (fun q (v, c) ->
            if d.(s).(v) <= w + c then q
            else begin
              d.(s).(v) <- w + c;
              IntMap.add (w + c)
                (v ::
                  try IntMap.find (w + c) q
                  with Not_found -> []) q
            end) q es.(u)) (IntMap.remove w q) us in
    dijkstra (IntMap.singleton 0 [s])
  done;
  Printf.printf "%d\n" @@
  Array.fold_left ( + ) 0 @@
  Array.init n @@ fun g ->
    d.(g).(g) <- 1000000000000000;
    Array.sort compare d.(g);
    Array.fold_left ( + ) 0 @@
    Array.init (n - 1) @@ fun i ->
      ( - ) (n - 1 - if r < t then 1 else 0) @@
      lower_bound (-1) (n - 1) @@ fun j -> d.(g).(i) * r < d.(g).(j) * t

Submission Info

Judge Result