let n, m, r, ans, ds, rs = Scanf.(scanf "%d %d %d" @@ fun n m r -> Array.(n, m, r, ref max_int, make_matrix n n (1 lsl 40), init r @@ fun _ -> scanf " %d" pred))
let s, fs, is, es = Array.(ref 0, make r false, make r 0, init m @@ fun _ -> Scanf.scanf " %d %d %d" @@ fun a b t -> ds.(a - 1).(b - 1) <- t; ds.(b - 1).(a - 1) <- t; a - 1, b - 1, t)
let rec f i = if i >= r then ans := min !ans !s else for j = 0 to r - 1 do if not fs.(j) then (fs.(j) <- true; is.(i) <- j; let d = if i > 0 then ds.(rs.(is.(i - 1))).(rs.(j)) else 0 in s := !s + d; f (i + 1); fs.(j) <- false; s := !s - d) done
let _ = Array.(iteri (fun i d -> iteri (fun j _ -> if i = j then d.(j) <- 0) d) ds); for k = 0 to n - 1 do for i = 0 to n - 1 do for j = 0 to n - 1 do ds.(i).(j) <- min ds.(i).(j) @@ ds.(i).(k) + ds.(k).(j) done done done; f 0; Printf.printf "%d\n" !ans