所以代码是计算每个殖民地的成本,其中地球是最上面的,就像一棵树,规则是叶子的成本是它们到达地球所需的成本,中间点它取决于他们可以去地球或需要经过他们才能到达地球的其他叶子,输入类似于这样 [(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