結果

問題 No.1 道のショートカット
ユーザー vjudge1
提出日時 2025-06-01 19:52:59
言語 Haskell
(9.10.1)
結果
RE  
実行時間 -
コード長 1,680 bytes
コンパイル時間 7,936 ms
コンパイル使用メモリ 180,480 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-06-01 19:53:12
合計ジャッジ時間 9,796 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 4
other RE * 40
権限があれば一括ダウンロードができます
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.10.1/environments/default
[1 of 2] Compiling Main             ( Main.hs, Main.o )
[2 of 2] Linking a.out

ソースコード

diff # 

import System.IO
import Data.Char (isSpace)

data Edge = Edge { to :: Int, cost :: Int, time :: Int } deriving Show
data State = State { node :: Int, usedCost :: Int, totalTime :: Int } deriving Show

shortestPath :: Int -> Int -> [[Edge]] -> Int
shortestPath n c graph =
    let maxVal = 1000000000 -- Simulating INT_MAX
        dp = [[maxVal | _ <- [0..c]] | _ <- [0..n-1]]
        dp' = updateDP dp [(0, 0, 0)] -- Start with node 0, cost 0, time 0
        updateDP d [] = d
        updateDP d ((currNode, currCost, currTime):rest) =
            let d' = if currTime < d !! currNode !! currCost then replace2D currNode currCost currTime d else d
                neighbors = [(to e, currCost + cost e, currTime + time e) | e <- graph !! currNode, currCost + cost e <= c]
                newStates = filter (\(n, c, t) -> t < d !! n !! c) neighbors
            in updateDP d' (rest ++ newStates)
        ans = minimum [dp' !! (n-1) !! i | i <- [0..c]]
    in if ans == maxVal then -1 else ans

replace2D :: Int -> Int -> Int -> [[Int]] -> [[Int]]
replace2D x y newVal matrix =
    take x matrix ++ [take y (matrix !! x) ++ [newVal] ++ drop (y + 1) (matrix !! x)] ++ drop (x + 1) matrix

parseInput :: IO ([[Edge]], Int, Int, Int)
parseInput = do
    [n, c, v] <- fmap (map read . words) getLine
    edges <- sequence [fmap (map read . words) getLine | _ <- [1..v]]
    let edgesProcessed = [(s-1, t-1, y, m) | [s, t, y, m] <- edges] -- Convert to zero-based indexing
    let graph = [[Edge t' y m | (s', t', y, m) <- edgesProcessed, s' == i] | i <- [0..n]]
    return (graph, n, c, v)

main :: IO ()
main = do
    (graph, n, c, _) <- parseInput
    print $ shortestPath n c graph
0