結果

問題 No.160 最短経路のうち辞書順最小
コンテスト
ユーザー aimy
提出日時 2017-07-22 14:16:02
言語 Haskell
(9.10.1)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,804 bytes
コンパイル時間 137 ms
コンパイル使用メモリ 150,528 KB
最終ジャッジ日時 2024-11-14 20:07:36
合計ジャッジ時間 479 ms
ジャッジサーバーID
（参考情報） 		judge5 / 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.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
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

ソースコード

diff # 

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