SRM659 div.2 500 PublicTransit

問題

http://community.topcoder.com/stat?c=problem_statement&pm=13793&rd=16462
R行C列のグリッド上に都市があり、距離をマンハッタン距離で計算するとする。
グリッド上に2つteleporterを設置して、その2つを距離0で移動できるとき、全点対の最大距離を最小に2つteleporterを配置したとき、その距離はいくらになるか

制約

0<=R<=10
0<=C<=10

解法

teleporterがおける全ての組み合わせを試せばよい。
iからjへの最短距離はmin(テレポートを使う場合,使わない場合)となる。
計算量はO( (R×C^4) (最大はO(10^8) )だけど、制限時間が5秒なのでC++なら間に合う。

コード

参戦記的な何か

250はソートして、最初の場所から順番に調べていくだけなのに、dfsしようとしてて書きなおしたら時間かかった。
それでこの500で、最初は全点対の距離をWashall-Floyd(O( (R×C)^3)、最大O(10^10))で求めようとしていた。まずpythonで書いてみて、テストケースが通ったけど最大ケース(10×10)でテストしたらTLEしてた。
急いでC++で書きなおしたが最大ケースだと通らない。結局提出できない。
Challenge Phaseで上の解法に気がつく。O(10^10))の人を狙い撃ちしたけど1hack1missだった。
その後、System Testで250がFailする。breakするのを忘れていた。