結果
問題 | No.2739 Time is money |
ユーザー | xsd |
提出日時 | 2024-04-20 21:00:05 |
言語 | OCaml (5.1.0) |
結果 |
AC
|
実行時間 | 568 ms / 2,000 ms |
コード長 | 1,135 bytes |
コンパイル時間 | 1,468 ms |
コンパイル使用メモリ | 22,000 KB |
実行使用メモリ | 57,984 KB |
最終ジャッジ日時 | 2024-04-20 21:00:17 |
合計ジャッジ時間 | 8,785 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 126 ms
19,200 KB |
testcase_03 | AC | 484 ms
50,176 KB |
testcase_04 | AC | 119 ms
18,816 KB |
testcase_05 | AC | 292 ms
36,864 KB |
testcase_06 | AC | 397 ms
45,696 KB |
testcase_07 | AC | 523 ms
49,664 KB |
testcase_08 | AC | 546 ms
55,936 KB |
testcase_09 | AC | 568 ms
57,984 KB |
testcase_10 | AC | 219 ms
28,800 KB |
testcase_11 | AC | 558 ms
57,728 KB |
testcase_12 | AC | 231 ms
27,776 KB |
testcase_13 | AC | 217 ms
27,648 KB |
testcase_14 | AC | 200 ms
27,648 KB |
testcase_15 | AC | 357 ms
39,552 KB |
testcase_16 | AC | 311 ms
31,360 KB |
testcase_17 | AC | 492 ms
44,544 KB |
testcase_18 | AC | 474 ms
44,416 KB |
testcase_19 | AC | 381 ms
48,384 KB |
ソースコード
Scanf.scanf "%d %d %d" (fun n m x -> let nei = Array.make n [] in for i = 1 to m do Scanf.scanf " %d %d %d %d" (fun u v c t -> let u = u - 1 in let v = v - 1 in nei.(u) <- (v, c + t * x) :: nei.(u); nei.(v) <- (u, c + t * x) :: nei.(v); ) done; let sentinel = max_int / 10 in let dist = Array.make n sentinel in dist.(0) <- 0; let module S = Set.Make (struct type t = int * int let compare = compare end) in let rec loop set = if S.is_empty set then dist.(n - 1) else let ((cost, pos) as mi) = S.min_elt set in let set = S.remove mi set in if dist.(pos) <> cost then loop set else let set = List.fold_left (fun set (next, c0) -> if dist.(next) > c0 + cost then (dist.(next) <- c0 + cost; S.add (c0 + cost, next) set) else set) set nei.(pos) in loop set in let v = loop (S.singleton (0, 0)) in Printf.printf "%d\n" @@ if v = sentinel then (-1) else (v + x - 1) / x )