0224-Bicycle Diet
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0224&lang=jp
問題概要
日本語なので略
考え方
ランドマークに経由地点としての意味しかない。
ダイクストラ法を用いて、家・市役所・ケーキ屋間の最短距離のみを求めてランドマークを消去する。
このとき、始点の場合を除いてケーキ屋から他の所に移動することは出来ないことに注意する。
家・市役所・ケーキ屋のみのグラフになったら循環セールスマン問題として解くことが出来るが、nが小さいのでBFSで充分。
計算量はO((2^n*n!)+(n+m)^2)だと思う。
