V8SORT - Sắp xếp
Tác giả: khuc_tuan
Ngôn ngữ: Java
import java.util.*;
public class Main {
static Map<int[], Integer> ma;
public static void main(String[] args) {
ma = new TreeMap<int[], Integer>(new Comparator<int[]>() {
public int compare(int[] a,int[] b) {
if(a.length!=b.length) return a.length-b.length;
for(int i=0;i<a.length;++i) if(a[i]!=b[i]) return a[i]-b[i];
return 0;
}
});
int N=0;
int[] a;
int[][] c;
Scanner sc = new Scanner(System.in);
String ss = sc.nextLine();
StringTokenizer st = new StringTokenizer(ss);
while(st.hasMoreTokens()) {
++N;
st.nextToken();
}
st = new StringTokenizer(ss);
a = new int[N];
c = new int[N][N];
for(int i=0;i<N;++i) a[i] = Integer.parseInt(st.nextToken());
for(int i=0;i<N;++i) for(int j=0;j<N;++j) c[i][j] = sc.nextInt();
Queue<int[]> q = new LinkedList<int[]>();
q.add(a);
ma.put( a, 0);
int result = 1000000000;
while(!q.isEmpty()) {
int[] u = q.remove();
int step = ma.get(u);
boolean ok = true;
for(int i=0;i<u.length-1;++i) if(u[i]>u[i+1]) ok = false;
if(ok) result = Math.min( result, step);
for(int i=0;i<u.length;++i) for(int j=i+1;j<u.length;++j) {
int[] v = u.clone();
int tt = v[i]; v[i] = v[j]; v[j] = tt;
if(ma.containsKey(v)) {
int oldStep = ma.get(v);
if(oldStep>step+c[i][j]) {
Integer I = step + c[i][j];
ma.put(v, I);
q.add(v);
}
}
else {
ma.put(v, step + c[i][j]);
q.add(v);
}
}
}
System.out.println(result);
}
}