Lost Treasure (UVa Live Archive Asia - 2008 Taipei(Taiwan))
問題
M*Nの盤面で図のように矩形の障害物がK個ある中で宝物を目的の場所まで動かしたい。宝物はR個の連結した矩形で表される。宝物を左右に動かすのに5$、上は10$、下は2$かかる時、宝物を目的の場所まで動かす最低コストを求めよ。
10<=M,N<=1000000
1<=K<=50
1<=R<=5
解法
宝物の矩形を1にするように逆に障害物を移動・拡大しKR個の矩形にする。後は座標圧縮してダイクストラをするだけ。
