結果

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

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)
0