import Control.Monad
import Control.Monad.ST
import Control.Monad.Primitive
import Data.Maybe
import qualified Data.ByteString.Char8 as BS
import Data.List
import Data.Char
import Data.Ord
import Data.Ix
import Data.Bool
import Data.Vector.Unboxed.Base
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
import qualified Data.Vector as V
import qualified Data.Vector.Mutable as VM
import Data.Array.Unboxed
import Data.Array.ST
import qualified Data.Sequence as Seq
import qualified Data.Set as Set
import qualified Data.IntMap as IM
data Heap a = Empty | Heap Int a (Heap a) (Heap a) deriving Show
empty = Empty
singleton' :: a -> Heap a
singleton' x = Heap 1 x Empty Empty
--併合
merge :: Ord a => Heap a -> Heap a -> Heap a
merge h Empty = h
merge Empty h = h
merge h1@(Heap _ x l1 r1) h2@(Heap _ y l2 r2)
| x < y = makeHeap x l1 (merge r1 h2)
| otherwise = makeHeap y l2 (merge r2 h1)
rank :: Heap a -> Int
rank Empty = 0
rank (Heap r _ _ _) = r
makeHeap :: a -> Heap a -> Heap a -> Heap a
makeHeap x a b
| ra >= rb = Heap (rb + 1) x a b
| otherwise = Heap (ra + 1) x b a
where ra = rank a
rb = rank b
--挿入
heapInsert :: Ord a => Heap a -> a -> Heap a
heapInsert h x = merge (singleton' x) h
--リストから
heapFromList :: Ord a => [a] -> Heap a
heapFromList = foldl heapInsert Empty
--リストへ
heapToList :: Ord a => Heap a -> [a]
heapToList h | isEmpty h = []
| otherwise = let (x, h') = deleteMin h in x : heapToList h'
--最小値の取り出し（削除）
deleteMin :: Ord a => Heap a -> (a, Heap a)
deleteMin Empty = error "Empty Heap"
deleteMin (Heap _ x a b) = (x, merge a b)
--最小値を見る（削除しない）
findMin :: Heap a -> a
findMin Empty = error "Empty Heap"
findMin (Heap _ x _ _) = x
--空か
isEmpty :: Heap a -> Bool
isEmpty Empty = True
isEmpty _ = False
readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine
main = do
[n, m] <- getIntList
as <- VU.fromList <$> getIntList
es <- fmap concat . replicateM m $ do
[u, v, b] <- getIntList
let vb = as VU.! (v-1)
ub = as VU.! (u-1)
return [(u-1, v-1, b + vb), (v-1, u-1, b + ub)]
let edge = V.create $ do
vec <- VM.replicate n []
forM_ es $ \(a, b, c) -> do
VM.modify vec ((c, b) :) a
return vec
let dist = VU.create $do
dvec <- VUM.replicate n (maxBound :: Int)
visited <- VUM.replicate n False
VUM.write dvec 0 0
VUM.write visited 0 True
let dijkstra Empty = return ()
dijkstra h = do
let ((c, v), h') = deleteMin h
vtd <- VUM.read visited v
if vtd
then dijkstra h'
else do
VUM.write visited v True
VUM.modify dvec (min c) v
m <- VUM.read dvec v
let next = edge V.! v
let f fh (fx, fv) = heapInsert fh (fx + m, fv)
let h'' = foldl f h' next
dijkstra h''
dijkstra $ heapFromList (edge V.! 0)
return dvec
d0 = as VU.! 0
putStrLn . unwords . map (\d -> show (d + d0)) . tail $ VU.toList dist
app/Main.hs:2:1: warning: [-Wunused-imports]
The import of ‘Control.Monad.ST’ is redundant
except perhaps to import instances from ‘Control.Monad.ST’
To import instances alone, use: import Control.Monad.ST()
|
2 | import Control.Monad.ST
| ^^^^^^^^^^^^^^^^^^^^^^^
app/Main.hs:3:1: warning: [-Wunused-imports]
The import of ‘Control.Monad.Primitive’ is redundant
except perhaps to import instances from ‘Control.Monad.Primitive’
To import instances alone, use: import Control.Monad.Primitive()
|
3 | import Control.Monad.Primitive
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
app/Main.hs:6:1: warning: [-Wunused-imports]
The import of ‘Data.List’ is redundant
except perhaps to import instances from ‘Data.List’
To import instances alone, use: import Data.List()
|
6 | import Data.List
| ^^^^^^^^^^^^^^^^
app/Main.hs:7:1: warning: [-Wunused-imports]
The import of ‘Data.Char’ is redundant
except perhaps to import instances from ‘Data.Char’
To import instances alone, use: import Data.Char()
|
7 | import Data.Char
| ^^^^^^^^^^^^^^^^
app/Main.hs:8:1: warning: [-Wunused-imports]
The import of ‘Data.Ord’ is redundant
except perhaps to import instances from ‘Data.Ord’
To import instances alone, use: import Data.Ord()
|
8 | import Data.Ord
| ^^^^^^^^^^^^^^^
app/Main.hs:9:1: warning: [-Wunused-imports]
The import of ‘Data.Ix’ is redundant
except perhaps to import instances from ‘Data.Ix’
To import instances alone, use: import Data.Ix()
|
9 | import Data.Ix
| ^^^^^^^^^^^^^^
app/Main.hs:10:1: warning: [-Wunused-imports]
The import of ‘Data.Bool’ is redundant
except perhaps to import instances from ‘Data.Bool’
To import instances alone, use: import Data.Bool()
|
10 | import Data.Bool
| ^^^^^^^^^^^^^^^^
app/Main.hs:11:1: warning: [-Wunused-imports]
The import of ‘Data.Vector.Unboxed.Base’ is redundant
except perhaps to import instances from ‘Data.Vector.Unboxed.Base’
To import instances alone, use: import Data.Vector.Unboxed.Base()
|
11 | import Data.Vector.Unboxed.Base
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
app/Main.hs:16:1: warning: [-Wunused-imports]
The import of ‘Data.Array.Unboxed’ is redundant
except perhaps to import instances from ‘Data.Array.Unboxed’
To import instances alone, use: import Data.Array.Unboxed()
|
16 | import Data.Array.Unboxed
| ^^^^^^^^^^^^^^^^^^^^^^^^^
app/Main.hs:17:1: warning: [-Wunused-imports]
The import of ‘Data.Array.ST’ is redundant
except perhaps to import instances from ‘Data.Array.ST’
To import instances alone, use: import Data.Array.ST()
|
17 | import Data.Array.ST
| ^^^^^^^^^^^^^^^^^^^^
app/Main.hs:18:1: warning: [-Wunused-imports]
The qualified import of ‘Data.Sequence’ is redundant
except perhaps to import instances from ‘Data.Sequence’
To import instances alone, use: import Data.Sequence()
|
18 | import qualified Data.Sequence as Seq
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
app/Main.hs:19:1: warning: [-Wunused-imports]
The qualified import of ‘Data.Set’ is redundant
except perhaps to import instances from ‘Data.Set’
To import instances alone, use: import Data.Set()
|
19 | import qualified Data.Set as Set
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
app/Main.hs:20:1: warning: [-Wunused-imports]
The qualified import of ‘Data.IntMap’ is redundant
except perhaps to import instances from ‘Data.IntMap’
To import instances alone, use: import Data.IntMap()
|
20 | import qualified Data.IntMap as IM
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
app/Main.hs:24:1: warning: [-Wmissing-signatures]
Top-level binding with no type signature: empty :: Heap a
|
24 | empty = Empty
| ^^^^^
app/Main.hs:24:1: warning: [-Wunused-top-binds]
Defined but not used: ‘empty’
|
24 | empty = Empty
| ^^^^^
app/Main.hs:58:1: warning: [-Wunused-top-binds]
Defined but not used: ‘heapToList’
|
58 | heapToList h | isEmpty h = []
| ^^^^^^^^^^
app/Main.hs:68:1: warning: [-Wunused-top-binds]
Defined but not used: ‘findMin’
|
68 | findMin Empty = error "Empty Heap"
| ^^^^^^^
app/Main.hs:73:1: warning: [-Wunused-top-binds]
Defined but not used: ‘isEmpty’
|
73 | isEmpty Empty = True
| ^^^^^^^
app/Main.hs:76:1: warning: [-Wmissing-signatures]
Top-level binding with no type signature:
readInt :: BS.ByteString -> Int
|
76 | readInt = fst . fromJust . BS.readInt
| ^^^^^^^
app/Main.hs:77:1: warning: [-Wmissing-signatures]
Top-level binding with no type signature:
readIntList :: BS.ByteString -> [Int]
|
77 | readIntList = map readInt . BS.words
| ^^^^^^^^^^^
app/Main.hs:78:1: warning: [-Wmissing-signatures]
Top-level binding with no type signature: getInt :: IO Int
|
78 | getInt = readInt <$> BS.getLine
| ^^^^^^
app/Main.hs:78:1: warning: [-Wunused-top-binds]
Defined but not used: ‘getInt’
|
78 | getInt = readInt <$> BS.getLine
| ^^^^^^
app/Main.hs:79:1: warning: [-Wmissing-signatures]
Top-level binding with no type signature: getIntList :: IO [Int]
|
79 | getIntList = readIntList <$> BS.getLine
| ^^^^^^^^^^
app/Main.hs:81:1: warning: [-Wmissing-signatures]
Top-level binding with no type signature: main :: IO ()
|
81 | main = do
| ^^^^
app/Main.hs:96:26: warning: [-Woperator-whitespace-ext-conflict]
The prefix use of a ‘$’ would denote an untyped splice
were the TemplateHaskell extension enabled.
Suggested fix: Add whitespace after the ‘$’.
|
96 | let dist = VU.create $do
| ^
app/Main.hs:110:25: warning: [-Wname-shadowing]
This binding for ‘m’ shadows the existing binding
bound at app/Main.hs:82:9
|
110 | m <- VUM.read dvec v
| ^