SRM383 Div2 1000

問題

山登りをする。
領域の地図が与えられ、その領域の高さが与えられる。ある領域から隣接する領域に行く為には高さの差がThreshold以下でなければならない。
もし行くことができる場合、より高い場所へ行く時はその差の2乗時間だけかかり、同じかより低い場所へ行く時は1時間だけかかる。
最初はホテルのある(0,0)からスタートし、より高い場所へ行って帰ってくることを考える。
しかし、日没までの時間timeToDark以内にホテルから出て帰ってこなければならない。
行くことのできる最大の高さを返す。

考え方

スタート(0,0)から各領域(i,j)に行く最短時間と帰る最短時間の和がtimeToDark以下であるような領域を見つける。最短時間はDijkstraすればいい。
(25*25)^3で怪しいと思ったけどWarshall-floydでも間に合った。

反省

計算量の見積もりとして、ループの中身が単純ならばワーシャルフロイドの(25*25)^3=244,140,625でもC++で500ms程度。
インクリメントを各1回ずつ入れてやると1s近くかかり、すごく怪しい。
10^6 : だいたい大丈夫。
10^7 : ぎりぎり大丈夫かも。中身が簡単な処理だけなら。最大ケースのチェックを忘れずに。
10^8 : かなり簡単な処理ならギリギリ大丈夫。(比較と代入ぐらいならセーフ)
10^9 : 別な方法を考えましょう。