結果

問題 No.160 最短経路のうち辞書順最小
ユーザー aimyaimy
提出日時 2017-07-07 10:41:15
言語 Haskell
(9.8.2)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,256 bytes
コンパイル時間 206 ms
コンパイル使用メモリ 150,528 KB
最終ジャッジ日時 2024-11-14 20:05:52
合計ジャッジ時間 648 ms
ジャッジサーバーID
（参考情報） 		judge4 / 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 ((!))
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

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 ((!))
import qualified Data.IntMap.Strict as M
import qualified Data.Set as S
import qualified Data.ByteString.Char8 as B
import Control.Monad
import Data.Maybe
import Data.List

type Cost = Int
type Vertex = Int

type Heap = S.Set (Cost, Vertex)
nullq = S.null
empty = S.empty 
push c v = S.insert (c,v)
pop = S.deleteFindMin

main = do
 [n,_,s,g] <- map read . words <$> getLine
 es <- map (map (fst . fromJust . B.readInt) . B.words) . B.lines <$> B.getContents
 putStrLn $ unwords $ map show (route n s g es)

route n s g es = unfoldr (backtrack imr) s ++ [g]
 where 
  imr = dijkstra t im0 q0
  t = foldl' (\acc [a,b,c] -> M.insertWith (++) b [(a,c)] (M.insertWith (++) a [(b,c)] acc)) M.empty es
  im0 = M.singleton g (0,[])
  q0 = push 0 g empty

backtrack im v = case im!v of
 (0,[]) -> Nothing
 (_,(vp:_)) -> Just (v,vp)

dijkstra t im q
 | nullq q = im
 | otherwise = dijkstra t im' q''
 where
  ((c0,v),q') = pop q
  im' = foldl' (\acc (b,c) -> M.insertWith mindic b (c0+c,[v]) acc) im vns
  q'' = foldl' (\acc (b,c) -> push (c0+c) b acc) q' vns
  vns = filter (\(b,c) -> M.notMember b im || c0+c <= fst (im!b)) (M.findWithDefault [] v t)

mindic (c1,v1@[v]) (c2,v2)
 | c1 < c2 = (c1,v1)
 | c1 == c2 = (c1, insert v v2)
0