/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
static int g[][] = {
{0, 1, 0, 1, 0},
{1, 0, 1, 1, 1},
{0, 1, 0, 0, 1},
{1, 1, 0, 0, 1},
{0, 1, 1, 1, 0}
};
static int dis[][] = {
{0, 2, 0, 1, 0},
{2, 0, 3, 3, 2},
{0, 3, 0, 0, 4},
{1, 3, 0, 0, 2},
{0, 3, 4, 2, 0}
};
static int[] p = new int[5];
static int min
= Integer.
MAX_VALUE; static HashSet<Integer> set = new HashSet<Integer>();
{
for(int i=0;i<p.length;i++){
p[i] = -1;
}
p[0] = 0;
HamiltonCycle(1, 0);
}
public static void HamiltonCycle(int pos, int sum){
if(pos == p.length){
if(g[p[pos-1]][0] == 1){
System.
out.
println("Cycle!!!"); min
= Math.
min(min, sum
); }
return;
}
for(int i=0;i<p.length;i++){
if(isSafe(i, pos)){
p[pos] = i;
set.add(i);
sum = sum+dis[i][p[pos-1]];
HamiltonCycle(pos+1, sum);
p[pos] = -1;
set.remove(i);
sum = sum-dis[i][p[pos-1]];
}
}
return;
}
public static boolean isSafe(int v, int pos){
if(g[p[pos-1]][v] == 0){
return false;
}
if(set.contains(v)){
return false;
}
return true;
}
}
LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KY2xhc3MgSWRlb25lCnsKCXN0YXRpYyBpbnQgZ1tdW10gPSB7CgkJCXswLCAxLCAwLCAxLCAwfSwgCiAgICAgICAgICAgIHsxLCAwLCAxLCAxLCAxfSwgCiAgICAgICAgICAgIHswLCAxLCAwLCAwLCAxfSwgCiAgICAgICAgICAgIHsxLCAxLCAwLCAwLCAxfSwgCiAgICAgICAgICAgIHswLCAxLCAxLCAxLCAwfQogICAgICAgIH07IAogICAgc3RhdGljIGludCBkaXNbXVtdID0gewoJCQl7MCwgMiwgMCwgMSwgMH0sIAogICAgICAgICAgICB7MiwgMCwgMywgMywgMn0sIAogICAgICAgICAgICB7MCwgMywgMCwgMCwgNH0sIAogICAgICAgICAgICB7MSwgMywgMCwgMCwgMn0sIAogICAgICAgICAgICB7MCwgMywgNCwgMiwgMH0KICAgICAgICB9OyAKCXN0YXRpYyBpbnRbXSBwID0gbmV3IGludFs1XTsKCXN0YXRpYyBpbnQgbWluID0gSW50ZWdlci5NQVhfVkFMVUU7CglzdGF0aWMgSGFzaFNldDxJbnRlZ2VyPiBzZXQgPSBuZXcgSGFzaFNldDxJbnRlZ2VyPigpOwoJcHVibGljIHN0YXRpYyB2b2lkIG1haW4gKFN0cmluZ1tdIGFyZ3MpIHRocm93cyBqYXZhLmxhbmcuRXhjZXB0aW9uCgl7CgkJZm9yKGludCBpPTA7aTxwLmxlbmd0aDtpKyspewoJCQlwW2ldID0gLTE7CgkJfQoJCXBbMF0gPSAwOwoJCUhhbWlsdG9uQ3ljbGUoMSwgMCk7CgkJU3lzdGVtLm91dC5wcmludGxuKG1pbik7Cgl9CglwdWJsaWMgc3RhdGljIHZvaWQgSGFtaWx0b25DeWNsZShpbnQgcG9zLCBpbnQgc3VtKXsKCQlpZihwb3MgPT0gcC5sZW5ndGgpewoJCQlpZihnW3BbcG9zLTFdXVswXSA9PSAxKXsKCQkJCVN5c3RlbS5vdXQucHJpbnRsbigiQ3ljbGUhISEiKTsKCQkJCVN5c3RlbS5vdXQucHJpbnRsbihBcnJheXMudG9TdHJpbmcocCkpOwoJCQkJbWluID0gTWF0aC5taW4obWluLCBzdW0pOwoJCQl9CgkJCXJldHVybjsKCQl9CgkJZm9yKGludCBpPTA7aTxwLmxlbmd0aDtpKyspewoJCQlpZihpc1NhZmUoaSwgcG9zKSl7CgkJCQlwW3Bvc10gPSBpOwoJCQkJc2V0LmFkZChpKTsKCQkJCXN1bSA9IHN1bStkaXNbaV1bcFtwb3MtMV1dOwoJCQkJSGFtaWx0b25DeWNsZShwb3MrMSwgc3VtKTsKCQkJCXBbcG9zXSA9IC0xOwoJCQkJc2V0LnJlbW92ZShpKTsKCQkJCXN1bSA9IHN1bS1kaXNbaV1bcFtwb3MtMV1dOwoJCQl9CgkJfQoJCXJldHVybjsKCQkKCX0KCXB1YmxpYyBzdGF0aWMgYm9vbGVhbiBpc1NhZmUoaW50IHYsIGludCBwb3MpewoJCWlmKGdbcFtwb3MtMV1dW3ZdID09IDApewoJCQlyZXR1cm4gZmFsc2U7CgkJfQoJCWlmKHNldC5jb250YWlucyh2KSl7CgkJCXJldHVybiBmYWxzZTsKCQl9CgkJcmV0dXJuIHRydWU7Cgl9Cn0=