夏への扉 (AOJ 2193)

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

問題

略

解法

実質的に3頂点のシュタイナー木を求める問題になる。なのでレノンのいる場所から頂点vまで行き、なつめのいる場所により、また元の位置vまで戻ってきて、夏への扉へ向かえば良い。なつめのいる位置から幅優先探索で各頂点への距離を前計算しておけばO(mlogm)でできる。BFS(or Dijkstra)を4回もしないといけなくてめんどい問題。