結果

問題 No.17 2つの地点に泊まりたい
ユーザー aimyaimy
提出日時 2017-07-20 12:31:02
言語 Haskell
(9.8.2)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,514 bytes
コンパイル時間 303 ms
コンパイル使用メモリ 150,784 KB
最終ジャッジ日時 2024-11-14 20:07:37
合計ジャッジ時間 693 ms
ジャッジサーバーID
（参考情報） 		judge2 / 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:2:1: error: [GHC-87110]
    Could not load module ‘Data.Map’.
    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 Data.Map ((!))
  | ^^^^^^^^^^^^^^^^^^^^^

Main.hs:3:1: error: [GHC-87110]
    Could not load module ‘Data.Map’.
    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.Map as M
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Main.hs:4: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.
  |
4 | import qualified Data.Set as S
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

ソースコード

diff # 

import Control.Monad
import Data.Map ((!))
import qualified Data.Map as M
import qualified Data.Set as S
import qualified Data.ByteString.Char8 as B
import Data.Maybe

type Vertex = Int
type Weight = Int
type Edge = ((Vertex, Vertex), (Weight, Path))
type Path = [Vertex]
type Memo = M.Map (Vertex, Vertex) (Weight, Path)

buildG :: [Edge] -> Memo
buildG = M.fromList

readUndirectedEdge :: B.ByteString -> [Edge]
readUndirectedEdge = concatMap ((\[s,t,w] -> [((s,t),(w,[s,t])),((t,s),(w,[t,s]))]) . map readVertex . B.words) . B.lines

readVertex :: B.ByteString -> Vertex
readVertex = fst . fromJust . B.readInt

main :: IO ()
main = do
  n <- readLn
  ss <- replicateM n readLn
  _ <- getLine
  es <- readUndirectedEdge <$> B.getContents
  let g = buildG es
  print (stay2 n ss g)

stay2 :: Int -> [Int] -> Memo -> Int
stay2 n ss = minimum . pay n ss . warshallFloyd n

pay :: Int -> [Int] -> Memo -> [Int]
pay n ss m = do
  s1 <- [1..n-2]
  s2 <- [1..n-2]
  guard (s1 /= s2)
  return (cost m 0 s1 + cost m s1 s2 + cost m s2 (n-1) + ss!!s1 + ss!!s2)

cost m s t = fst (m!(s,t)) 

warshallFloyd :: Int -> Memo -> Memo
warshallFloyd n m = foldl short m [(k,i,j) | k<-[0..n-1], i<-[0..n-1], j<-[0..n-1]]

short m (k,i,j) = M.insertWith lexmin (i,j) (connect m k i j) m

connect m k i j = maybe (100000,[]) id $ do
  (w1,p1) <- M.lookup (i,k) m
  (w2,p2) <- M.lookup (k,j) m
  return (w1 + w2, init p1 ++ tail p2)

lexmin (w1,p1) (w2,p2)
  | w1 < w2 = (w1, p1)
  | w1 == w2 = (w1, min p1 p2)
  | otherwise = (w2,p2)
0