Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
1.8 kB
2
Indexable
Never
import java.util.Scanner;

public class Main {
    int[] x;
    int f;
    int fmin;
    boolean[] visited;
    int load;
    int K;
    int n;
    int[][] c; // distance matrix
    public void input() {
        Scanner in = new Scanner(System.in);
        n = in.nextInt(); K = in.nextInt();
        c = new int[2*n+1][2*n + 1];
        for(int i = 0; i <= 2*n; i++)
            for (int j = 0; j <= 2*n; j++)
                c[i][j] = in.nextInt();
    }

    private  boolean check(int v, int k) {
        if (visited[v])  return false;
        if (v <= n) {
            if (visited[v + n]) return false;
            if (load >= K) return false;
        }else {
            if (!visited[v - n] ) return false;
        }
        return true;
    }

    public void solve() {
        x = new int[2*n+1]; x[0] = 0; f = 0; fmin = 1000000; load = 0;
        visited = new boolean[2*n+1];
        for (int v = 1; v <= 2*n; v++) visited[v] = false;
        tryValue(1);
        System.out.println(fmin);
    }

    private void solution() {
        if (f + c[x[2*n]][x[0]] < fmin) {
            fmin = f + c[x[2*n]][x[0]];
        }
    }


    private void tryValue(int k) {
        for (int v = 1; v <= 2*n; v++) {
            if (check(v, k)) {
                x[k] = v; visited[v] = true; f = f + c[x[k-1]][x[k]];
                if (v <= n) load += 1; else load -= 1;
                if (k == 2*n) solution();
                else {
                    tryValue(k + 1);
                }
                if (v <= n) load -= 1; else load += 1;
                visited[v] = false; f = f - c[x[k-1]][x[k]];

            }
        }
    }
    public static void main(String[] args) {
        Main p = new Main();
        p.input();
        p.solve();
    }
}
Leave a Comment