UVa 12841 - In Puzzleland (III)

Source

Second UVa regional warmup（20141101）
UVa 12841

問題概要

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

テストケースの数 $T$ は $T \leq 60$ を満たす
$1 \leq N \leq 15$

解法

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

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

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

Current time: 2024年04月19日17時57分11秒
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)