結果
問題 | No.845 最長の切符 |
ユーザー | pekempey |
提出日時 | 2019-06-28 22:02:34 |
言語 | OCaml (5.2.1) |
結果 |
AC
|
実行時間 | 263 ms / 3,000 ms |
コード長 | 765 bytes |
コンパイル時間 | 295 ms |
コンパイル使用メモリ | 21,704 KB |
実行使用メモリ | 13,952 KB |
最終ジャッジ日時 | 2024-10-09 00:45:43 |
合計ジャッジ時間 | 3,314 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
let n, m = Scanf.scanf "%d %d" (fun x y -> x, y);; let inf = max_int / 4;; let g = Array.make_matrix n n (-inf);; for i = 1 to m do let a, b, c = Scanf.scanf " %d %d %d" (fun x y z -> x-1, y-1, z) in g.(a).(b) <- max g.(a).(b) c; g.(b).(a) <- max g.(b).(a) c; done;; let dp = Array.make_matrix (1 lsl n) (n) (-inf);; for i = 0 to n - 1 do dp.(1 lsl i).(i) <- 0; done;; for i = 0 to (1 lsl n) - 1 do for j = 0 to n - 1 do for k = 0 to n - 1 do if (i lsr k) mod 2 == 0 then dp.(i lor (1 lsl k)).(k) <- max dp.(i lor (1 lsl k)).(k) (dp.(i).(j) + g.(j).(k)); done done done;; let ans = ref (-inf);; for i = 0 to (1 lsl n) - 1 do for j = 0 to n - 1 do ans := max !ans dp.(i).(j); done done;; Printf.printf "%d\n" !ans;;