1004

問題原文

問題

与えられた無向グラフに対して 3 点以上(全部の点を含む必要はない)からなる閉路のうち距離の和が最小のものを求める.ただし,同じ点を複数回通ってはならない.

なお,2 点間の辺の数は 1 つとは限らない.

解法

2 点間の辺の数は 1 つとは限らないが,同じ点を 2 度以上通ってはならないことから,ある 2 点間については一度しか通過することがない.したがって,距離最小の辺だけとっておけば大丈夫.

ここまでやった後,泉は任意の 2 点 ij について辺 (i,j) を含まないグラフにおける最短経路を Dijkstra 法で探索した.この最短経路に辺 (i,j) を加えたものが i からはじまり最後に j を通るような閉路のうちで最短のものとなる.ただし,(既知の閉路長)<(辺 (i,j) の距離)のときは枝を刈らないと時間切れになる.

泉のプログラム

file1004.cpp


添付ファイル: file1004.cpp 532件 [詳細]

Last-modified: 2009-11-06 (金) 13:25:51 (3426d)