2217
問題文（要約）
図中の９本の道路のうち１本に対して工事を行った結果、その道路の移動時間が短くなったため、A村からF村まで９時間以下で行ける経路が４通りになった。工事は、全ての道路について、移動時間が０.５時間短くなるごとに同一の費用がかかり、これを単位に最小の費用で行われた。このとき、工事後における、最長経路と最短経路の所要時間の差はいくらか。ただし、同じ村を２回以上通ることはできず、道路の移動時間を０.５時間未満にはできない。また村での滞在時間は考えない。
- ６時間
- ６.５時間
- ７時間
- ７.５時間
- ８時間
答案を書くことは実際要求されてませんが、この問題の思考過程を過不足なく記述するのがすこし難しかった印象。すこしだけ答案の補足訂正をします。
（１）のとこはMaxとminが共有する道路、つまりBC,EFのことを言ってます。BC,EFを工事してもMax-minが10で一定であることが言いたかった。なので、右ページのCB,EFは調べる必要がないです。（２）はMaxとminが通らない道路を工事した場合、Maxルートに変動はないけど9.0以下のminは開拓されることを言っててその差が10以上であることを示してる。（３）はminのみが通る道路AB,CE,EFについて述べていて、そこを工事するとminが8.5以下になってその差が10.5以上になるよね、ってことを示してる。だから、工事を行う道路は（工事前の）Maxのみが通る道路AD,DC,BEに絞られる。
そして、右ページでその3本について調べれば、BEを通ってAからFまで行くルートが3本しかなく不適なので、ADを工事すればいいことがわかる。このとき、ADCBEF＝15となり、MaxルートがABECDF＝16のルートに変更されていることに注意したい。
