Submission #71197448

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
int N;
int E[16][16];
int memo[16][1 << 16];
int calc(int pos, int left) {
  int ans = -1;
  int i;
  if (left == 0) return E[pos][0];
  if (memo[pos][left]) return ~memo[pos][left];
  for (i = 0; i < N; i++) {
    if ((left >> i) & 1) {
      int candidate = calc(i, left & ~(1 << i)) + E[pos][i];
      if (ans < 0 || candidate < ans) ans = candidate;
    }
  }
  return ~(memo[pos][left] = ~ans);
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>

int N;
int E[16][16];

int memo[16][1 << 16];

int calc(int pos, int left) {
	int ans = -1;
	int i;
	if (left == 0) return E[pos][0];
	if (memo[pos][left]) return ~memo[pos][left];
	for (i = 0; i < N; i++) {
		if ((left >> i) & 1) {
			int candidate = calc(i, left & ~(1 << i)) + E[pos][i];
			if (ans < 0 || candidate < ans) ans = candidate;
		}
	}
	return ~(memo[pos][left] = ~ans);
}

int main(void) {
	int i, j;
	if (scanf("%d", &N) != 1) return 1;
	for (i = 0; i < N - 1; i++) {
		for (j = i + 1; j < N; j++) {
			if (scanf("%d", &E[i][j]) != 1) return 1;
			E[j][i] = E[i][j];
		}
	}
	if (N == 2) {
		puts("0 0");
	} else {
		printf("%d %d\n", N, calc(0, (1 << N) - 2));
	}
	return 0;
}

/*

道路N-1本では、良くて木にしかならず、この状態では頂点を1個外すとダメになる所がありそう
道路N本で、ぐるっとすれば、条件を満たす (十分条件) → 多分最小本数

※ただしN=2のときは頂点1個外すと1個だけになるので、適当な道路1本あればいい
(というかそもそも道路の候補が1本しかないだろう)
↑嘘……ではないが、「残りの全地区」でいいので、道路はなくてもいい

道路N本でぐるっとしない → 多分次数1の頂点ができて、そこに繋がるところを消すと死ぬ

最初の地域からスタートして、適当な順でたどって、最後の地域から最初の地域に戻る

*/

Submission Info

Judge Result