1004 †問題 †与えられた無向グラフに対して 3 点以上(全部の点を含む必要はない)からなる閉路のうち距離の和が最小のものを求める.ただし,同じ点を複数回通ってはならない. なお,2 点間の辺の数は 1 つとは限らない. 解法 †2 点間の辺の数は 1 つとは限らないが,同じ点を 2 度以上通ってはならないことから,ある 2 点間については一度しか通過することがない.したがって,距離最小の辺だけとっておけば大丈夫. ここまでやった後,泉は任意の 2 点 i,j について辺 (i,j) を含まないグラフにおける最短経路を Dijkstra 法で探索した.この最短経路に辺 (i,j) を加えたものが i からはじまり最後に j を通るような閉路のうちで最短のものとなる.ただし,(既知の閉路長)<(辺 (i,j) の距離)のときは枝を刈らないと時間切れになる. 泉のプログラム † |