結果
問題 | No.160 最短経路のうち辞書順最小 |
ユーザー | aimy |
提出日時 | 2017-07-22 14:16:02 |
言語 | Haskell (9.8.2) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,804 bytes |
コンパイル時間 | 127 ms |
コンパイル使用メモリ | 150,272 KB |
最終ジャッジ日時 | 2024-04-27 02:28:04 |
合計ジャッジ時間 | 472 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.8.2/environments/default [1 of 2] Compiling Main ( Main.hs, Main.o ) Main.hs:1:1: error: [GHC-87110] Could not load module ‘Data.Set’. It is a member of the hidden package ‘containers-0.6.8’. Use -v to see a list of the files searched for. | 1 | import qualified Data.Set as S | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Main.hs:2:1: error: [GHC-87110] Could not load module ‘Data.IntMap’. It is a member of the hidden package ‘containers-0.6.8’. Use -v to see a list of the files searched for. | 2 | import qualified Data.IntMap as M | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
ソースコード
import qualified Data.Set as S import qualified Data.IntMap as M import qualified Data.ByteString.Char8 as B import qualified Data.Array.IArray as A import Data.Maybe type Vertex = Int type Weight = Int type Edge = (Vertex, (Vertex, Weight)) type Path = [Vertex] type Graph = A.Array Vertex (S.Set (Vertex, Weight)) type Memo = M.IntMap (Weight, Path) type PriorityQueue = S.Set (Weight, Vertex) empty = S.empty isEmpty = S.null singleton = S.singleton insert = S.insert deleteFindMin = S.deleteFindMin readUndirectedEdge :: B.ByteString -> [Edge] readUndirectedEdge = concatMap ((\[v,w,l] -> [(v,(w,l)),(w,(v,l))]) . map readVertex . B.words) . B.lines readVertex :: B.ByteString -> Vertex readVertex = fst . fromJust . B.readInt buildG :: Int -> [Edge] -> Graph buildG n = A.accumArray (flip S.insert) S.empty (0, n-1) from :: Graph -> Vertex -> S.Set (Vertex, Weight) from g = (g A.!) main :: IO () main = do [n,_,vs,vg] <- map read . words <$> getLine es <- readUndirectedEdge <$> B.getContents let g = buildG n es putStrLn $ unwords $ map show (route g vs vg) route :: Graph -> Vertex -> Vertex -> Path route g vs vg = vs : r where (_,r) = imr M.! vs imr = dijkstra g vg -- accumrated weight and lexical order shortest path dijkstra :: Graph -> Vertex -> Memo dijkstra g s = dijkstraCore g q0 m0 where q0 = singleton (0, s) m0 = M.singleton s (0, []) dijkstraCore :: Graph -> PriorityQueue -> Memo -> Memo dijkstraCore g q m | isEmpty q = m | otherwise = dijkstraCore g q2 m1 where ((w0, s), q1) = deleteFindMin q p = s : snd (m M.! s) m1 = S.foldr (\(t,w) acc -> M.insertWith min t (w0+w,p) acc) m vns q2 = S.foldr (\(t,w) acc -> insert (w0+w, t) acc) q1 vns vns = S.filter (\(t,w) -> M.notMember t m || w0+w <= fst (m M.! t)) (from g s)