16pts,剩下全WA,不知道拿错了QAQ
#include <bits/stdc++.h>
using namespace std;
const int N = 20;
int n, m, w[N][N], dp[N][1 << N];
int dfs(int u, int vis, int y) {
//printf("%d %d %d\n", u, vis, y);
if (u == n - 1 && vis < (1 << n) - 1) return INT_MIN;
if (vis == (1 << n) - 1 && u == n - 1) return y;
if (dp[u][vis] != INT_MIN) return dp[u][vis];
for (int i = 0; i < n; ++i) {
if (vis >> i & 1 || w[u][i] == INT_MIN) continue ;
dp[u][vis] = max(dp[u][vis], dfs(i, vis | (1 << i), y + w[u][i]));
}
return dp[u][vis];
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
w[i][j] = INT_MIN;
while (m--) {
int u, v, ww;
scanf("%d%d%d", &u, &v, &ww);
w[u][v] = max(w[u][v], ww);
}
for (int i = 0; i < 1 << n; ++i)
for (int j = 0; j < n; ++j)
dp[j][i] = INT_MIN;
printf("%d", dfs(0, 1, 0));
return 0;
}