Haskellでも書いてみた

メモライズと聞いては、Haskellを出さないわけには行かない。
いろいろやっているうちに30行を切った。
あの、苦戦したD問題がこんな小さなコードになってしまったよ。
実行時間は12秒ぐらいなので十分現実的なコードだろう。

import Control.Monad
import Data.Bits

main = do
  ns@[n,m,p,a,b] <- getNums
  if all (==0) ns then return ()
   else do
    cs <- getNums
    gs <- replicateM p getNums
    putStrLn $ solve (ns,cs,gs)
    main
  where getNums = liftM (map read . words) getLine

solve ([n,m,p,a+1,b+1],cs,gs) = if ret>inf-1 then "Impossible" else show ret
  where
    ret = tbl!!a!!0
    tbl = [[f c u | u <- [0..]] | c <- [0..] ]
    f cur use
      | cur == b  = 0
      | otherwise = minimum $ inf :
        [ tbl!!t!!(use .|. bit u) + fromIntegral (g!!cur!!t) / fromIntegral (cs!!u)
        | t <- [0..m-1], g!!cur!!t >= 0, u <- [0..n-1], use .&. bit u == 0]

    g = foldl (\g [f+1,t+1,c] -> wrmat t f c $ wrmat f t c g)
          (replicate m $ replicate m (-1)) gs
    wrmat a b c xs = wrvec a (wrvec b c (xs!!a)) xs
    wrvec 0 c (x:xs) = (c:xs)
    wrvec a c (x:xs) = (x:wrvec (a-1) c xs)
    inf = 1e10