250
二つの独立な事象A,Bのどちらかがおこる確率は 1-(1-事象Aがおこる確率)*(1-事象Bがおこる確率)で出る
500
まず最初に移動可能な集合とその移動にかかる時間を計算する。あとは入口にいる人の集合と地図がどちらにあるかの状態に関してダイクストラすればよい。
1000
GかSかどっちかだけならば単なる二部マッチングの問題になるのは分かったのだけど、(G*S)を右側に持ってくるとグラフが大きくなりすぎるので単なる二部マッチングではだめで、source->G->W->S->sinkというグラフを作って最大流を流す必要がある。時間内には思いつかなかった。
