課題は毎年変わるのですが、私が受講したときは、そのなかに 「グラフを使った自由プログラム」というものが入っていたので、 それに使用しました。
Subject: report1
Date: Mon, 07 Sep 1998 11:29:41 +0900
From: IIJIMA 'Delmonta' Hiromitsu <g740564@komaba.ecc.u-tokyo.ac.jp>
Organization: The University of tokyo
Newsgroups:lectures.g98.cp2-yamaguch-S-Thu-1
２年理１・１５組の いいじま です。
＃というより、相談員の、といったほうが分かりやすいかな？計算機プログラミングII レポート課題（１）グラフ
例によって(^_^;) 鉄道の問題です。が、
ので、今回のプログラムは「改札内乗り換え」、 別名「キセル乗車経路案内」(^_^;)です。
- 運賃計算はあまりにも定番
- 乗り換え案内は複雑すぎる
＃（厳重注意）このプログラムは、あくまでも知的ゲームの域に
＃とどめてください。キセル乗車は犯罪です(^_^;)実は、首都圏の大手鉄道各線は、ほとんどが改札を出ることなく乗り換え可能です。（もちろん時間も運賃も通常よりかかりますが。） たとえば、渋谷駅で山手線外回りから京王井の頭線に乗り換えるには、 通常は山手線の玉川改札を出てから井の頭線の改札に入りますが、 下のルートを通ると、改札を出ることなく、 山手線ホームから井の頭線ホームに到達できます。
渋谷 山手線外回り→（日暮里）→常磐線快速 北千住 営団千代田線 代々木上原 小田急線 下北沢 京王井の頭線このプログラムでは、このような乗り換えルートのうち、 乗り換え回数のもっとも少ないものをひとつ表示します。 ただし JR 線内の乗り換えはカウントしません。 また京王本線と井の頭線の乗り換えもカウントしません。
アルゴリズムは単純な幅優先探索ですが、それほど規模が大きくないので、 本来は queue を使うべきところですが手抜きで使っていません。
関連ファイルはすべて ~g740564/cp2/graph/ に入っていて、
です。ファイル名に
- ソースプログラム:
*.cpp,Makefile- 実行形式 ECC 用:
report_graph-euc.exec- 実行形式 Win 95 用:
report_graph-sj.exe- データファイル:
railnetwork-euc.dat,railnetwork-sj.dat-sjがついているのがシフト JIS 形式で Windows 用（ただし、改行コードは\nだけなので、メモ帳やtypeコマンドなどでは読めません。 C 言語環境に付属のエディタや WWW ブラウザなどで読めます）、-eucがついているのが EUC 形式で ECC 用です。 中身は同じです。なお、路線名はすべて全角文字で入力してください。 ECC で実行する場合は、Mule から Kterm へ切り張るか、 Mule から M-x
shellで実行してください。出力例（ＪＲ新宿駅から西武新宿駅へ） 出発地の路線名>ＪＲ ←全角で入力する。 目的地の路線名>西武新宿 ←「線」の文字はつけない ＪＲ 線 西船橋／中野 営団東西 線 日本橋 営団銀座 線 赤坂見附（永田町） 営団有楽町 線 小竹向原-練馬 西武池袋 線 所沢 西武新宿 線☆-- 飯嶋 浩光 ----------------------------------------------☆ ｜IIJIMA 'Delmonta' Hiromitsu an der Universitaet Tokyo ｜ ｜ http://www.komaba.ecc.u-tokyo.ac.jp/~g740564 ｜ ☆----------------------- g740564@komaba.ecc.u-tokyo.ac.jp --☆
（注）この例で「JR 線→(拝島)→西武拝島線→(小平)→西武新宿線」 という結果が出ないのは、当時は拝島駅の構造が確認できなかったため、 「拝島駅改札内で JR と西武がつながっている」 という情報を敢えて入れなかったためです。
実際の拝島駅では、西武のホームと JR のホームが平行線になっており、 片方の改札が西武管理、もう片方が JR 管理になっています。 どちらの改札でもパスネット・イオカード・スイカがすべて使用可能です。