提出 #12073938
ソースコード 拡げる
import Control.Exception (assert) import Control.Monad import qualified Control.Monad.ST as ST import qualified Data.Array.IO as IO import qualified Data.Array.ST as ST import qualified Data.Array.Unboxed as A import Data.Bits import qualified Data.ByteString.Char8 as BS import Data.Char import Data.Foldable import Data.List import Data.Maybe import qualified Data.Sequence as Seq import qualified Data.Set as Set import qualified Data.Vector as VB import qualified Data.Vector.Mutable as VBM import qualified Data.Vector.Unboxed as V import qualified Data.Vector.Unboxed.Mutable as VM import Debug.Trace readInt = fst . fromJust . BS.readInt readIntList = map readInt . BS.words getInt = readInt <$> BS.getLine getIntList = readIntList <$> BS.getLine getIntVec n = V.unfoldrN n (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine readInteger = fst . fromJust . BS.readInteger readIntegerList = map readInteger . BS.words getInteger = readInteger <$> BS.getLine getIntegerList = readIntegerList <$> BS.getLine -- (node, dist) type Graph_dijk = VB.Vector (V.Vector (Int, Int)) dijkstra :: Int -> Graph_dijk -> Int -> IO (V.Vector Int) dijkstra s g numV = do let inf = 10^9 :: Int d <- VM.new numV VM.set d inf VM.write d s 0 -- tuple represent (min distance, node id) let set = Set.singleton (0, s) loop :: Set.Set (Int, Int) -> IO () loop set | Set.null set = return () | otherwise = do let ((mdist, v), set') = Set.deleteFindMin set edges = g VB.! v d_v <- VM.read d v if d_v < mdist then loop set' else do set'' <- loop2 v edges 0 set' loop set'' loop2 :: Int -> V.Vector (Int, Int) -> Int -> Set.Set (Int, Int) -> IO (Set.Set (Int, Int)) loop2 v edges j set | j >= V.length edges = return set | otherwise = do let e = edges V.! j v_to = fst e cost = snd e d_v <- VM.read d v d_to <- VM.read d v_to let cond = d_to > d_v + cost set' = if cond then (d_v + cost, v_to) `Set.insert` set else set when cond $ VM.write d v_to (d_v + cost) loop2 v edges (j+1) set' loop set V.freeze d main = do [n, m, t] <- getIntList as <- getIntVec n g <- VBM.new n g_rev <- VBM.new n VBM.set g ([] :: [(Int, Int)]) VBM.set g_rev ([] :: [(Int, Int)]) replicateM m $ do [a, b, c] <- getIntList let (a', b') = (a-1, b-1) xs <- VBM.read g a' ys <- VBM.read g_rev b' VBM.write g a' ((b', c):xs) VBM.write g_rev b' ((a', c):ys) g' <- VB.freeze g g_rev' <- VB.freeze g_rev let g'' = VB.map V.fromList g' g_rev'' = VB.map V.fromList g_rev' costs <- dijkstra 0 g'' n costs_r <- dijkstra 0 g_rev'' n let solve i r | i >= n = r | otherwise = let waste = (costs V.! i) + (costs_r V.! i) rest = max 0 (t - waste) gain = rest * as V.! i in solve (i+1) (max r gain) print $ solve 0 0
提出情報
提出日時 | |
---|---|
問題 | D - トレジャーハント |
ユーザ | unnohideyuki |
言語 | Haskell (GHC 7.10.3) |
得点 | 100 |
コード長 | 3549 Byte |
結果 | AC |
実行時間 | 611 ms |
メモリ | 71036 KB |
ジャッジ結果
セット名 | Sample | Subtask1 | All | ||||||
---|---|---|---|---|---|---|---|---|---|
得点 / 配点 | 0 / 0 | 50 / 50 | 50 / 50 | ||||||
結果 |
|
|
|
セット名 | テストケース |
---|---|
Sample | 00_example_01.txt, 00_example_02.txt, 00_example_03.txt |
Subtask1 | 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 50_small_01.txt, 50_small_02.txt, 50_small_03.txt, 50_small_04.txt, 50_small_05.txt, 50_small_06.txt, 50_small_07.txt, 50_small_08.txt, 50_small_09.txt, 50_small_10.txt, 60_hand_01.txt, 60_hand_02.txt, 60_hand_03.txt, 60_hand_04.txt, 70_max_01.txt, 70_max_02.txt, 70_max_03.txt |
All | 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 10_rand_01.txt, 10_rand_02.txt, 10_rand_03.txt, 10_rand_04.txt, 10_rand_05.txt, 10_rand_06.txt, 10_rand_07.txt, 10_rand_08.txt, 10_rand_09.txt, 10_rand_10.txt, 10_rand_12.txt, 10_rand_13.txt, 30_max_01.txt, 30_max_02.txt, 30_max_03.txt, 30_max_04.txt, 30_max_05.txt, 30_max_06.txt, 40_corner_01.txt, 40_corner_02.txt, 40_corner_03.txt, 40_corner_04.txt, 50_small_01.txt, 50_small_02.txt, 50_small_03.txt, 50_small_04.txt, 50_small_05.txt, 50_small_06.txt, 50_small_07.txt, 50_small_08.txt, 50_small_09.txt, 50_small_10.txt, 60_hand_01.txt, 60_hand_02.txt, 60_hand_03.txt, 60_hand_04.txt, 70_max_01.txt, 70_max_02.txt, 70_max_03.txt |
ケース名 | 結果 | 実行時間 | メモリ |
---|---|---|---|
00_example_01.txt | AC | 2 ms | 380 KB |
00_example_02.txt | AC | 2 ms | 380 KB |
00_example_03.txt | AC | 2 ms | 508 KB |
10_rand_01.txt | AC | 7 ms | 2940 KB |
10_rand_02.txt | AC | 66 ms | 11260 KB |
10_rand_03.txt | AC | 12 ms | 4732 KB |
10_rand_04.txt | AC | 3 ms | 2044 KB |
10_rand_05.txt | AC | 13 ms | 5500 KB |
10_rand_06.txt | AC | 12 ms | 6652 KB |
10_rand_07.txt | AC | 20 ms | 9084 KB |
10_rand_08.txt | AC | 7 ms | 3964 KB |
10_rand_09.txt | AC | 18 ms | 8188 KB |
10_rand_10.txt | AC | 4 ms | 1916 KB |
10_rand_12.txt | AC | 181 ms | 25852 KB |
10_rand_13.txt | AC | 159 ms | 22012 KB |
30_max_01.txt | AC | 410 ms | 54140 KB |
30_max_02.txt | AC | 611 ms | 70012 KB |
30_max_03.txt | AC | 289 ms | 52732 KB |
30_max_04.txt | AC | 425 ms | 44412 KB |
30_max_05.txt | AC | 423 ms | 44284 KB |
30_max_06.txt | AC | 422 ms | 44284 KB |
40_corner_01.txt | AC | 227 ms | 70140 KB |
40_corner_02.txt | AC | 230 ms | 70524 KB |
40_corner_03.txt | AC | 230 ms | 70780 KB |
40_corner_04.txt | AC | 268 ms | 71036 KB |
50_small_01.txt | AC | 4 ms | 1404 KB |
50_small_02.txt | AC | 2 ms | 636 KB |
50_small_03.txt | AC | 2 ms | 636 KB |
50_small_04.txt | AC | 2 ms | 1020 KB |
50_small_05.txt | AC | 6 ms | 2044 KB |
50_small_06.txt | AC | 5 ms | 1660 KB |
50_small_07.txt | AC | 2 ms | 508 KB |
50_small_08.txt | AC | 2 ms | 508 KB |
50_small_09.txt | AC | 3 ms | 1276 KB |
50_small_10.txt | AC | 2 ms | 1020 KB |
60_hand_01.txt | AC | 2 ms | 380 KB |
60_hand_02.txt | AC | 2 ms | 380 KB |
60_hand_03.txt | AC | 2 ms | 508 KB |
60_hand_04.txt | AC | 2 ms | 380 KB |
70_max_01.txt | AC | 69 ms | 18940 KB |
70_max_02.txt | AC | 69 ms | 19324 KB |
70_max_03.txt | AC | 69 ms | 19324 KB |