街を駆ける道 (AOJ 2334)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2334

問題

略

解法

街ABか街CDのどちらかは直接道を作ったほうが良い。なので両方試してダイクストラとかで最短距離を計算すれば良い。