UVa 12841 - In Puzzleland (III)

Source

Second UVa regional warmup(20141101)
UVa 12841

問題概要

ノード数 $N$ の無向グラフが与えられる.
また,各ノードにはそれぞれ異なるアルファベット大文字が $1$ 文字書かれている.
ノード $1$ からノード $N$ まで,全てのノードを $1$ 度だけ通って移動するパスの中で,通った順にアルファベットを繋げた $N$ 文字が辞書順最小となるものを求める問題.
そのようなパスが存在しないならそれを指摘する.

解法

DP+経路復元.
状態を(今まで訪れたノードの集合,最後に訪れたノード)を状態として,そのような状況が達成可能かどうかを計算していく.
時間計算量は $O(T N^2 2^N)$ 程度.

C++によるスパゲッティなソースコード

この部分を表示するには表示権限を持つユーザーでログインする必要があります.


Current time: 2017年07月24日15時46分20秒
Last modified: 2014年11月08日19時24分21秒 (by laycrs)
Tags: Competitive_Programming UVa_Online_Judge UVa_Contest_20141101_1
トップページに戻る

Logged in as: unknown user (not login)

ログイン: