AOJ 2334 - 街を駆ける道

問題
提出コード

解法

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