課題４＆５

プログラムは、git pullすれば現れるかと思います。

本来の問題（オプション課題）

タクシーが長い距離を移動する。

都市の距離関係を示すグラフが与えられている
- タクシーは開始点からゴールに移動
- ガスステーションは少数（グリーンの都市）
- 満タンにしても、指定した距離しか移動できない(cap x 10 しか移動できない, cap: タンクの容量)
質問：移動距離を最小にするには？(到達不能の場合は -1 を返す)

例えば、下の図の例だと、cap=34 なら、Tokyo, Niigata, Toyama, Kyoto と移動するのが正解で、cap=33なら到達不能となるわけです。

課題5B図

簡単のため、ガスタンクの容量は無限大ということにしましょう。つまり、給油（ガス？）の心配はしないで、開始点からゴールの最短経路を求めましょうという問題です。

これなら、素直な最短経路問題です。正解は、545 となります。

都市が文字列として与えられていますが、C でこの種の処理は大変なので、先に都市番号を割り振ってあります。都市の数はcityNumに格納し、都市には、起点を 0, 終点が 1, それ以外の都市には、2以上 cityNum-1以下の整数値を出現順に割り当ててあります。

皆さんの作成する関数はint solve(int n, int m, int cap)

関数int solve(int n, int m, int cap)
- n: 道の数
- m: ガスステーションの数（オプション課題でのみ利用）
- cap: ガスタンクの容量(移動可能距離は cap*10, 都市間距離が cap*10以下であれば到達可能)（オプション課題でのみ利用）
- 返り値：起点から終点まで到達可能なら最小経路長を返す。到達不能な場合は、-1 を返す。

大域変数として下記が準備してあります。当然、各自でデータ構造を追加・拡張してもらって構いません。

struct roadinfo (roadinfo_t): 各都市につながる道の情報を保持
- num: 道の数
- struct { int dest; int dist; } roads[]: 道の配列。dest は行き先、distは距離。
大域配列 roadinfo_t roadinfo[MAX_N_CITIES]: 上記の配列
大域配列 cityNames[]: 各都市の名前を格納（デバッグ用途以外では使わない）
大域配列 bool withGas[MAX_N_CITIES]: withGas[index]の値は、都市番号(index)の都市に、ガスステーションあるか(値:1)、ないか(値:0)を示す。（オプション課題でのみ利用）

main 関数で正解チェックをおこなっています。

注: オプション問題を解く場合は、optionF = 1 に変更して動作させてください。sample0.ans や D0.ans など 0 がついているのが、簡単化した問題の正解ファイルで、0 がつかないものは本来の問題の正解ファイルです。

プログラム自身は 30行以内で完成するかと思います。ただ、デバッグなど大変かもしれません。

正解プログラム例は、1月に入ってから公開する予定です。

正解プログラム例の公開までは、一般の提出となります。以下を提出してください。
- プログラムファイル
- レポート：学番＋氏名＋実行結果（debug 出力が混ざっていても構いません）
  - 課題４は、追加したデータ構造などの簡単な説明を入れてください。
- アピールポイントがある人は、その旨解説入れてください。
- ほとんどのデータで正解しているが、一部データでバグが取れない場合は、その旨記述して、考察を記載してください。
正解例を参考にレポートを提出する場合
- まず、未完成でも、その自作プログラムを提出すること。
- 自分が作成できなかった部分がどの部分か、正解例ではどのように実現されていたか、解説すること。
- 正解プログラム例の実行を、デバッガなどでトレースし、正しく動作していることを説明すること。今回の例では、sample.in の最初の例について解説すれば OK です。

まずは、sample.in の問題をきちんと解きましょう。デバッガで動作を追っかけるとよいでしょう。

D.in で問題を間違えた場合は、当該問題とその回答を sample.in や sample0.ans 冒頭にコピーするなりして、デバッグするとよいでしょう。

余力のある人は取り組んでください。難易度は、かなり上がります。まず、解き方の基本方針を考えてみましょう。

12/20 の授業でヒントを出す予定ですが、それまでにできた人は早めに提出しましょう。加点します。

提出物