hotpepsiの練習帳

TCO12 Round 2C

23:30

Easy (300) GreedyTravelingSalesman

問題

• セールスマンがN個の都市を0から順番にまわる。
• 全ての都市は、片方向の道路が両方向で用意されており、どの都市からどの都市へも移動できる。
• セールスマンは、未訪問の都市のうち、コストが最小の道路を選んで移動する。
• 各道路のコストが与えられる。ただし道路の1つが工事中のため、1～9999の間で変化する可能性がある。
• 最悪のコストを求める。

方針

• 道路の変化は一度だけで、かつ、最初に起きるとしてよい (sampleより)
• 変化前の最短経路を求めておく
• 最短経路のうち、1箇所が変化する
• 単純に考えると、そのうちの1つが9999になる
• それだけでsampleのいくつかが通るが、合わない
• 全ての経路を1～9999に変化させる全試行でも求まるが、もちろん間に合わない
• 変化するパターンを列挙すると、(1)最短経路のコストが高くなり、別の経路にいく(2)最短経路のコストが高くなるが、同じ経路のまま(3)別の経路のコストが低くなり、別の経路にいく、の3通り
• (1)は最短経路のコストを9999にする
• (2)は最短経路のコストを、最低コスト近辺で試す (同じコストの場合indexが小さいほうが選ばれるため、それを考慮して1を調整する)
• (3)は別の経路のコストを最小値に変更する (マイナス1の調整は(2)と同じ)
• マイナス1調整した場合、最小のコストは1なのに注意する
• BFSでもっと単純に書ける
• https://github.com/firewood/topcoder/blob/master/tco_2012/GreedyTravelingSalesman.cpp

結果

0pt 539th rating 1302 -> 1299 (-3)

3回連続0点なので反省。

練習としては、sample7が通るように書いたらsystem testも通ったので、まあまあ。