解法
明らかに、線分と
が交差しない場合は、それぞれの街を直接結ぶのが一番距離が短くて済みます。
つまり、今回考えるべきなのは、と
が交差する場合になります。
このとき、仮にの経路を、
と交差しないように迂回して作成したとすると、どのように迂回しても、
については、そのまま直接結べることがわかります。これは
が遠回りになった場合も同様です。
ので、,
のうちどちらかは直接結んだまま、もう片方を遠回りの経路にした際の最小コストが求まればよいです。
遠回りの経路は、直接結んだ線分と交差しないようにしつつ、ダイクストラ法を用いることで計算できます。
