Submission #1846155

---

Source Code Expand

#include <cstdio>
#include <cstring>
#include <cassert>
#include <algorithm>
using namespace std;

#define iter(i, n) for (int i = 1; i <= n; ++i)
#define iter0(i, n) for (int i = 0; i < n; ++i)

const int inf = 1e9;

int n, m, U, M, f[20][1 << 15], h[20][1 << 15], g[20][20], ws[1 << 15];

int dfs(int x, int s);

int dfs2(int x, int s) {
	//printf("!!%d %d\n", x, s);
	assert(s >> x & 1);
	if (s == U) {
		return x == n - 1 ? 0 : -inf;
	}
	int &w = h[x][s];
	if (w != -1) return w;
	w = -inf;
	iter0(i, n) if (!(s >> i & 1) && g[x][i]) {
		w = max(w, g[x][i] + dfs(i, s));
	}
	//if (x == 0 && s == 29)	printf("h[%d][%d]=%d %d\n", x, s, h[x][s], s >> (n - 1) & 1);
	return w;
}
int sum = 0;
int dfs(int x, int s) {
//	printf("!d %d %d\n", x, s);
	int &w = f[x][s];
	if (w != -1) return w;
	w = -inf;
	int t = U - s;
	for (int _t = t; _t; _t = (_t - 1) & t) {
		if (_t >> x & 1) {
			w = max(w, ws[_t] + dfs2(x, s | _t));
		//	if (x == 1 && s == 29) printf("%d %d %d %d %d\n", x, s, _t, sum - dfs2(x, s | _t) - ws[_t], ws[_t]);
		}
	}
//	printf("f[%d][%d]=%d\n", x, s, sum - f[x][s]);
	return w;
}

int main() {
	//freopen("78F.in", "r", stdin);
	memset(f, -1, sizeof(f));
	memset(h, -1, sizeof(h));
	scanf("%d%d", &n, &m);
	M = 1 << n;
	U = M - 1;
	
	iter(i, m) {
		int x, y, c;
		scanf("%d%d%d", &x, &y, &c); --x, --y;
		g[x][y] = g[y][x] = c;
		sum += c;
	}

	iter0(s, M) {
		iter0(i, n) if (s >> i & 1) {
			iter0(j, i) if (s >> j & 1) ws[s] += g[i][j];
		}
		//printf("!%d %d\n", s, ws[s]);
	}

	printf("%d\n", sum - dfs(0, 0));
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:52:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
                       ^
./Main.cpp:58:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &x, &y, &c); --x, --y;
                              ^

Judge Result