AOJ 2334 Roads on Towns

解法

実は,A->B と C->D の少なくともどちらか一方は,直接結んでしまって良いことがわかる.そうすればあとは最短経路問題.

以下は自分のイメージ.
例えば図のように,(解が存在し,かつ)コストを最小化するためには青が迂回しなければならないケースを考える.
このとき,赤の始点と終点は,書かれている星のいずれかの2つの位置関係にあるはず.
もし左の2つの位置関係なら,青は迂回する必要がないのでおかしい.
もし上の2つの位置関係なら,赤は迂回する必要がある(か,直接結べる).直接結べない場合,その迂回ルートは,青の点線を通ることはできない.もしどのように迂回しても点線を通る場合は,同時に青の実線も通る必要が有るためである.
下の2つの位置関係なら,図のように直接結べる.
以上から,もし可能な答えが存在するなら,どちらかは直接結べば良いことがわかる.
f:id:Suikaba:20170627143155p:plain