慶應SFC　総合政策学部　情報入試　2017年　大問Ⅲ　過去問解説

(ア)
新宿→湘南台が30人だから、新宿→湘南台→SFCで30人運べばよい。
湘南台→SFCで運べるのはあと40人。

次に、新宿→横浜→湘南台→SFCで、横浜→湘南台が30人なのでこの経路で30人運ぶ。
新宿→横浜で運べるのはあと50人。
湘南台→SFCで運べるのはあと10人。

次に、新宿→横浜→藤沢→湘南台→SFCで湘南台→SFCが10人なのでこの経路で10人運ぶ。
新宿→横浜で運べるのはあと40人。
横浜→藤沢で運べるのはあと40人。
藤沢→湘南台で運べるのはあと40人。

最後に新宿→横浜→辻堂→SFCで30人運ぶ。
それぞれの経路が余裕がある。

総費用は
760×30 + 1120×30 + 1370×10 + 1380×30 = 111500円
となる。

(イ)
(ア)で、まず新宿→湘南台→SFCで30人運ぶ。
湘南台→SFCで運べるのはあと40人。

次に、新宿→横浜→藤沢→湘南台→SFCで、湘南台→SFCで運べるのが40人なのでこの経路で40人運ぶ。
新宿→横浜で運べるのはあと40人。
横浜→藤沢で運べるのはあと10人。
藤沢→湘南台で運べるのはあと10人。

最後に新宿→横浜→辻堂→SFCで30人運ぶ。
それぞれの経路が余裕がある。

総費用は
760×30 + 1370×40 + 1380×30 = 119000円

(ウ)
(81)(3)が正しい。「vに対し」とあるので、vに関わる値であることは想像できる。(5)にすると、「無限大」とつながらない。よって(3)。
(82)(4)が正しい。uは「Qからcostvが最安になる場所」、vは「uから直接行ける場所」である。処理Bで、それまでに求めたと、新たに求めたvまでの費用(新宿からuまでの費用)+length(u,v)(uからvまでの費用)を比較し、もし新たに求めたvまでの費用が安い場合はの数値を置き換えて、vまでの最安の費用をに残す処理を行う。
(83)(5)が正しい。を+length(u,v)とする場合、uを経由してvに行く経路が最安となるので、の値をuにする処理を行う。

(エ)
新宿軽油は使えない。
横浜→湘南台も使えない。
湘南台→SFCも使えない。
よって、東京→横浜→辻堂→SFCとなる。
1300×20=26000円増える。
137500円。