移動の方法を全て試そうとすると、訪問する駅の順番のパターンは10000!通りとなるので明らかに試すことができません。
最短となる可能性のある経路について考えると、これは 以下の4通りに絞られることがわかります。
- スタート地点から右回りで回りきる
- スタート地点から左回りで回りきる
- スタート地点から途中まで右回りで回り、残りを左回りで回りきる
- スタート地点から途中まで左回りで回り、残りを右回りで回りきる
1.と2.については1通りしかありません。始点から回って最後に到達する駅までの長さが経路長になります。
3.と4.に関しては折り返す場所として考えられる点はM個あるのでM通りとなります。折り返す前と後の経路の長さはそれぞれ別々に引き算で求めて構わないので、別々に求めた後に足すとよいです。
最終的に、4つのうち最も短い経路長に100をかけたものが答えになります。
参考文献：4つの言語で解ける 実践プログラミング問題集