結果
問題 | No.2739 Time is money |
ユーザー |
|
提出日時 | 2024-04-20 21:00:05 |
言語 | OCaml (5.2.1) |
結果 |
AC
|
実行時間 | 647 ms / 2,000 ms |
コード長 | 1,135 bytes |
コンパイル時間 | 1,467 ms |
コンパイル使用メモリ | 22,016 KB |
実行使用メモリ | 57,984 KB |
最終ジャッジ日時 | 2024-10-12 19:10:00 |
合計ジャッジ時間 | 10,396 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
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 )