# Untitled

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 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 (k == 2*n) solution();
else {
tryValue(k + 1);
}