An Asian Preliminary Regional(20151205)
(ICPC Dhaka 2015 Preliminary)
UVa 13030
ICPCのジャッジ団が人気商品を食べにレストランに行く.
ICPCの本部の大学はノード $0$ であり,レストランは $N$ 個あり,ノード $1$ から $N$ に割り振られている.
また,枝 $M$ 個が与えられ,つながっているノード間を双方向に移動でき,枝 $i$ を移動するのにかかる時間は $W_i$ である.
同じノード間には高々 $1$ 個の枝しかない.
また,ノード $i$ のレストランにおいて,その人気商品が食べられる確率 $P_i$ が与えられる,
それは,何回訪れようと,独立に,同じ確率 $P_i$ で人気商品が食べられる.
ジャッジ団は,制限時間 $T$ を決めた後,以下のアルゴリズムによって,レストランを訪ねて行く.
人気商品を食べられる確率と,終了してノード $0$ に帰るまでにかかる時間の期待値を求める問題.
動的計画法で,状態を(現在時刻,今いる場所)として,その確率を計算していく.
制約から推測される通り,枝は自己ループがありうるので注意.
ノード $0$ からの最短距離は最初に $1$ 回ダイクストラして計算しておく.
時間計算量は $O(T(N+M)+M \log N))$ 程度で,ダイクストラの代わりにワーシャルフロイドして $O(T(N+M)+N^3)$ でも十分通る.
この部分を表示するには表示権限を持つユーザーでログインする必要があります.
Current time: 2024年04月20日05時00分23秒
Last modified: 2015年12月16日01時19分04秒 (by laycrs)
Tags: Competitive_Programming UVa_Online_Judge UVa_Contest_20151205_1
トップページに戻る
Logged in as: unknown user (not login)