次のような形式で始点と終点のある重み付き有向グラフを定義することにする。
最初の行には、グラフの始点の名前が書かれている。
次の行には、グラフの終点の名前が書かれている。
以後は、各行が辺を意味している。辺は、辺の始点、終点、重みがスペースを区切りとして並んだものである。
辺の重みは正の整数であるとする。
例えば、次のようなものがグラフの表現である。
A
F
A B 3
A C 1
A E 12
B A 5
B C 1
B D 8
C D 10
C E 8
D F 2
E F 4
辺の重みを2点間の移動にかかるコストと考えることにする。この表現によるグラフをファイル入力から読み込み(ファイル名は"graph.txt"とする事標準入力から受け取るとする事。標準入力から与えられる入力には、".txt" も含まれる。ファイル名は50文字以下として良い。)、グラフの始点からグラフの終点までの移動コストを最小にする経路を求め、その経路上の点を始点から順に終点まで、改行を区切りとして表示するプログラムをCで作成せよ。始点から終点に到達可能でない場合は、「(no route)」と表示せよ。該当する経路が複数存在する場合には、それらのうち1つだけを表示するものとする。点名の文字数は99以下、点の総数と辺の総数はそれぞれ1000以下、辺の重みの総和がintの範囲を超えないと仮定してよい。
実行例: 少し大きなグラフのサンプルを配布しておく。このサンプルを入力として与えた場合の出力は以下の通りである。
渋谷
表参道
青山一丁目
永田町
四ツ谷
市ケ谷
飯田橋
春日
本郷三丁目
締切: 01/06 23:59
2つの文字列をキーボード入力から受け取った時に、動的計画法によってそれらの最長共通部分列を求めるアルゴリズムを実装し、その最長共通部分列を表示するプログラムを作成せよ。最長共通部分列が複数考えられる場合には、どれか一つのみ表示すれば良い。
注意: 表示するものは、最長共通部分列の長さではなく、最長共通部分列である。最長共通部分列の定義は、「アルゴリズムとデータ構造」の講義で利用している教科書によるものとする。
入力例
AFFEACEDCA
DDFCFCBDA
出力例
FFCDA
締切: 01/06 23:59