結果
問題 | No.160 最短経路のうち辞書順最小 |
ユーザー | aimy |
提出日時 | 2017-07-18 18:16:56 |
言語 | Haskell (9.8.2) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,884 bytes |
コンパイル時間 | 223 ms |
コンパイル使用メモリ | 149,760 KB |
最終ジャッジ日時 | 2024-11-14 20:07:29 |
合計ジャッジ時間 | 640 ms |
ジャッジサーバーID (参考情報) |
judge4 / 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.IntMap’. 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 Data.IntMap (IntMap, (!)) | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 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 | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Main.hs:3: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. | 3 | import qualified Data.Set as S | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
ソースコード
import Data.IntMap (IntMap, (!)) import qualified Data.IntMap as M import qualified Data.Set as S import qualified Data.ByteString.Char8 as B import qualified Data.Array.IArray as A import Data.Maybe type Vertex = Int type Cost = Int type Edge = (Vertex, (Vertex, Cost)) type Path = [Vertex] type Graph = A.Array Vertex (S.Set (Vertex, Cost)) type Heap = S.Set (Cost, Vertex) nullq :: Heap -> Bool nullq = S.null empty :: Heap empty = S.empty push :: Cost -> Vertex -> Heap -> Heap push c v = S.insert (c,v) pop :: Heap -> ((Cost, Vertex), Heap) pop = 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, Cost) 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 ! vs imr = dijkstra g q0 im0 im0 = M.singleton vg (0,[]) q0 = push 0 vg empty dijkstra :: Graph -> Heap -> IntMap (Cost, Path) -> IntMap (Cost, Path) dijkstra g q im | nullq q = im | otherwise = dijkstra g q'' im' where ((c0,v),q') = pop q r = v : snd (im ! v) im' = S.foldr (\(b,c) acc -> M.insertWith mindic b (c0+c,r) acc) im vns q'' = S.foldr (\(b,c) acc -> push (c0+c) b acc) q' vns vns = S.filter (\(b,c) -> M.notMember b im || c0+c <= fst (im!b)) (from g v) mindic :: (Cost, Path) -> (Cost, Path) -> (Cost, Path) mindic (_,[]) (_,_) = undefined mindic (c1,r) (c2,v2) | c1 < c2 = (c1, r) | otherwise = (c1, min r v2)