ＥＸＣＥＬによる最長片道ルート探索：東京メトロ編

1.　問題を解く際のルール

ＪＲの最長片道ルート探索の応用問題として、「東京メトロ大回り乗車」の最長ルートをＥＸＣＥＬのソルバーによって計算してみようと思う。
「東京メトロ大回り乗車」は、「東京メトロの乗車ルートは同一駅を通過しない限り最短経路で計算する」というルールを活用して初乗り運賃の切符でどこまで長い距離を乗車できるかという遊びのことである。

1. 東京メトロの初乗り運賃１６０円で乗車できるのは、最短距離で６�qまでである。つまり、終点駅は起点駅から最短距離で６�q以内にある必要がある。
   
2. ラッチ外乗換駅（下記９箇所）での乗換えは、起点から乗換駅までの運賃が初乗り運賃である場合にのみ可能である。
   　　* 上野（銀座線と日比谷線）
   　　* 大手町（丸ノ内線と東西線・千代田線及び東西線と半蔵門線）
   　　* 池袋（丸ノ内線と有楽町線）
   　　* 飯田橋（東西線と有楽町線・南北線）
   　　* 日比谷・有楽町（日比谷線・千代田線と有楽町線）
   　　* 淡路町・新御茶ノ水（丸ノ内線と千代田線）
   　　* 三越前（銀座線と半蔵門線）
   　　* 九段下（東西線と半蔵門線）
   　　* 上野広小路・仲御徒町（銀座線と日比谷線）
   
3. 運賃計算上同一駅とみなされる異名乗換駅（上野広小路・仲御徒町、溜池山王・国会議事堂前、淡路町・新御茶ノ水、赤坂見附・永田町、日比谷・有楽町）はそこで相互間を乗り継がなければ別駅とみなす。