0

所以代码是计算每个殖民地的成本，其中地球是最上面的，就像一棵树，规则是叶子的成本是它们到达地球所需的成本，中间点它取决于他们可以去地球或需要经过他们才能到达地球的其他叶子，输入类似于这样 [(1,2,5);(2,3,15)....], 'a' 是第一个行星，'b' 是目的地行星，'c' 是在这两者之间进行旅行所需的成本，然后通过更多输入创建一棵树。

let p = read_int() (*Input com o numero de planetas*)
  (*let () = if p < 0 then failwith "Valor Incorreto" Verifica se o numero de planetas é pelo menos positivo*)

let m = read_int() (*Input com o numero de wormholes*)
  let () = if m < p-1 || m > p || m = p then failwith "Valor Incorreto" (*Verifica se o numero de wormholes e -1 c*)

let buracos = Array.make m (0, 0, 0) (*Cria o tuplo com os inputs*)

let conexoes m buracos = (*Le os inputs e coloca em tuplos*)
  for i = 0 to m - 1 do
     buracos.(i) <- Scanf.scanf  " %d %d %d" (fun a b c -> a, b, c)
  done

let colonias lburacos p =
    let x = List.filter (fun (a, _, _) -> a = p) lburacos
    in List.map (fun (_, b, c) -> (b, c)) x

let () = conexoes m buracos 

let lburacos = Array.to_list buracos

let resultados = Array.make p 0

let pais buracos p =
  let x = List.filter (fun (_, b, _) -> b = p) buracos
  in List.map (fun (a, _, c) -> (a, c)) x

let rec calc_raizes buracos p custo =
  let anteriores = pais buracos p in
    List.iter (fun (a, c) -> resultados.(a - 1) <- max resultados.(a - 1) (custo + c); calc_raizes buracos a (custo + c)) anteriores

let rec calc_folhas buracos p custo =
  let proximos = colonias buracos p in
    if proximos = [] then calc_raizes buracos p 0
    else List.iter (fun (a, b) -> resultados.(a - 1) <- custo + b; calc_folhas buracos a (custo + b)) proximos

let () = calc_folhas lburacos 1 0
let () = resultados.(0) <- Array.fold_left max 0 resultados 

let () = Array.iter (Printf.printf "%d\n") resultados
4

1 回答 1

0

两个提示：

  • 您多次重新计算节点的邻域，并且每次都遍历整个边列表。您应该一劳永逸地计算所有顶点的邻域（也称为邻接矩阵），并且遍历边列表一次。

  • 您可以计算一次而不是两次的距离。特别是，calc_raizes不必要且效率低下（每个叶子都会重新访问其所有祖先）。

于 2021-06-21T11:14:54.117 回答