結果

問題 No.160 最短経路のうち辞書順最小
ユーザー aimyaimy
提出日時 2017-07-18 13:19:58
言語 Haskell
(9.8.2)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,083 bytes
コンパイル時間 158 ms
コンパイル使用メモリ 150,656 KB
最終ジャッジ日時 2024-11-14 20:07:31
合計ジャッジ時間 504 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、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.Strict’.
    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.Strict (IntMap, (!))
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Main.hs:2:1: error: [GHC-87110]
    Could not load module ‘Data.IntMap.Strict’.
    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.Strict 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
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

ソースコード

diff # 

import Data.IntMap.Strict (IntMap, (!))
import qualified Data.IntMap.Strict 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
import Data.List

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 = unfoldr (backtrack imr) vs ++ [vg]
 where 
  imr = dijkstra g q0 im0
  im0 = M.singleton vg (0,[])
  q0 = push 0 vg empty

backtrack :: IntMap (Cost, Path) -> Vertex -> Maybe (Vertex, Vertex)
backtrack im v = case im!v of
 (_,[]) -> Nothing
 (_,(vp:_)) -> Just (v,vp)

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
  im' = S.foldr (\(b,c) acc -> M.insertWith mindic b (c0+c,[v]) 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,v1@(v:_)) (c2,v2)
 | c1 < c2 = (c1,v1)
 | c1 == c2 = (c1, insert v v2)
 | otherwise = undefined
0