Submission #676838

Source Code Expand

Copy
```let rec tabulate n f =
let rec loop acc m =
if m < n then loop (f m :: acc) (m + 1)
else List.rev acc in
loop [] 0

let make_edge n abcs =
let edge = Array.make n [] in
List.iter (fun (a, b, c) ->
edge.(a) <- (b, c) :: edge.(a)) abcs;
edge

let rec dikjstra ( +. ) q edge d =
match q with
| [] -> ()
| u :: q ->
let u, q =
List.fold_left (fun (u, q') u' ->
if d.(u) < d.(u') then (u, u' :: q') else (u', u :: q')) (u, []) q in
List.iter (fun (v, c) ->
d.(v) <- min d.(v) (d.(u) +. c)) edge.(u);
dikjstra ( +. ) q edge d

let () =
let n, m, t = Scanf.scanf "%d %d %d\n" (fun n m t -> n, m, t) in
let as_ = Array.init n (fun _ -> Scanf.scanf "%d " (fun a -> a)) in
let abcs = tabulate m (fun _ ->
Scanf.scanf "%d %d %d\n" (fun a b c -> a - 1, b - 1, c)) in
let d = Array.make n 1145141919 in
d.(0) <- 0;
dikjstra ( + ) (tabulate n (fun i -> i)) (make_edge n abcs) d;
let d' = Array.make n 1145141919 in
d'.(0) <- 0;
dikjstra ( + ) (tabulate n (fun i -> i))
(make_edge n (List.map (fun (a, b, c) -> (b, a, c)) abcs)) d';
tabulate n (fun i ->
as_.(i) * (t - d.(i) - d'.(i)))
|> List.fold_left max 0
|> Printf.printf "%d\n"
```

#### Submission Info

Submission Time 2016-03-26 23:18:52+0900 D - トレジャーハント fetburner OCaml (4.02.3) 50 1268 Byte TLE

#### Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 00_example_01.txt, 00_example_02.txt, 00_example_03.txt
Subtask1 50 / 50 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 50_small_01.txt, 50_small_02.txt, 50_small_03.txt, 50_small_04.txt, 50_small_05.txt, 50_small_06.txt, 50_small_07.txt, 50_small_08.txt, 50_small_09.txt, 50_small_10.txt, 60_hand_01.txt, 60_hand_02.txt, 60_hand_03.txt, 60_hand_04.txt, 70_max_01.txt, 70_max_02.txt, 70_max_03.txt
All 0 / 50 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 10_rand_01.txt, 10_rand_02.txt, 10_rand_03.txt, 10_rand_04.txt, 10_rand_05.txt, 10_rand_06.txt, 10_rand_07.txt, 10_rand_08.txt, 10_rand_09.txt, 10_rand_10.txt, 10_rand_12.txt, 10_rand_13.txt, 30_max_01.txt, 30_max_02.txt, 30_max_03.txt, 30_max_04.txt, 30_max_05.txt, 30_max_06.txt, 40_corner_01.txt, 40_corner_02.txt, 40_corner_03.txt, 40_corner_04.txt, 50_small_01.txt, 50_small_02.txt, 50_small_03.txt, 50_small_04.txt, 50_small_05.txt, 50_small_06.txt, 50_small_07.txt, 50_small_08.txt, 50_small_09.txt, 50_small_10.txt, 60_hand_01.txt, 60_hand_02.txt, 60_hand_03.txt, 60_hand_04.txt, 70_max_01.txt, 70_max_02.txt, 70_max_03.txt
Case Name Status Exec Time Memory
00_example_01.txt 4 ms 384 KB
00_example_02.txt 4 ms 384 KB
00_example_03.txt 4 ms 384 KB
10_rand_01.txt
10_rand_02.txt
10_rand_03.txt
10_rand_04.txt
10_rand_05.txt
10_rand_06.txt
10_rand_07.txt
10_rand_08.txt
10_rand_09.txt
10_rand_10.txt
10_rand_12.txt
10_rand_13.txt
30_max_01.txt
30_max_02.txt
30_max_03.txt 1562 ms 30464 KB
30_max_04.txt
30_max_05.txt
30_max_06.txt
40_corner_01.txt
40_corner_02.txt
40_corner_03.txt
40_corner_04.txt
50_small_01.txt 8 ms 1792 KB
50_small_02.txt 4 ms 512 KB
50_small_03.txt 6 ms 1152 KB
50_small_04.txt 5 ms 896 KB
50_small_05.txt 12 ms 2944 KB
50_small_06.txt 9 ms 2304 KB
50_small_07.txt 5 ms 1024 KB
50_small_08.txt 4 ms 384 KB
50_small_09.txt 6 ms 1152 KB
50_small_10.txt 5 ms 640 KB
60_hand_01.txt 4 ms 384 KB
60_hand_02.txt 4 ms 384 KB
60_hand_03.txt 4 ms 384 KB
60_hand_04.txt 4 ms 384 KB
70_max_01.txt 103 ms 11904 KB
70_max_02.txt 102 ms 11904 KB
70_max_03.txt 107 ms 11904 KB