結果
問題 | No.1 道のショートカット |
ユーザー |
![]() |
提出日時 | 2020-08-08 03:32:53 |
言語 | Haskell (9.10.1) |
結果 |
AC
|
実行時間 | 178 ms / 5,000 ms |
コード長 | 1,542 bytes |
コンパイル時間 | 10,929 ms |
コンパイル使用メモリ | 181,044 KB |
実行使用メモリ | 7,168 KB |
最終ジャッジ日時 | 2024-07-20 16:51:11 |
合計ジャッジ時間 | 12,462 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.8.2/environments/default [1 of 2] Compiling Main ( Main.hs, Main.o ) [2 of 2] Linking a.out
ソースコード
import qualified Control.Monad as Monad import qualified Data.ByteString.Char8 as BSC8 import qualified Data.Char as Char import qualified Data.List as List getInt :: IO [Int] getInt = List.unfoldr f <$> BSC8.getLine where f s = do (n, s') <- BSC8.readInt s return (n, BSC8.dropWhile Char.isSpace s') getMultiLineInt :: Int -> IO [[Int]] getMultiLineInt n = Monad.replicateM n getInt main :: IO () main = do n <- readLn :: IO Int c <- readLn :: IO Int _ <- readLn :: IO Int xs <- map _func . List.transpose <$> getMultiLineInt 4 print $ solver n c xs type City = Int type Time = Int type Money = Int inf :: Int inf = 1000000007 _func :: [Int] -> ((City, City), (Money, Time)) _func (a:b:c:d:_) = ((a, b), (c, d)) _func _ = error "error" from :: ((City, City), (Money, Time)) -> City from = fst . fst to :: ((City, City), (Money, Time)) -> City to = snd . fst cost :: ((City, City), (Money, Time)) -> Money cost = fst . snd time :: ((City, City), (Money, Time)) -> Time time = snd . snd solver :: Int -> Int -> [((City, City), (Money, Time))] -> Int solver n c xs = if ans < inf then ans else -1 where ans = solver' 1 c solver' m c' | m == n = 0 | otherwise = foldr min inf [(table !! ((to r) - 1) !! (c' - (cost r))) + (time r) | r <- es] where es = [r | r <- xs, (from r) == m, c' - (cost r) >= 0] table = [[solver' k d | d <- [0..c]] | k <- [1..n]]