状态压缩DP 初巧遇

#include <bits/stdc++.h>

using namespace std;
#define INF 0x7ffffff
#define maxn 20

int n;
int dp[1<<maxn][maxn];
int d[maxn][maxn];

int dfs(int S, int v)
{
    if(dp[S][v] != -1) return dp[S][v];

    if(S==(1<<n)-1 && v==0)
        return dp[S][v] = 0;

    int res = INF;
    for(int u=0; u<n; u++)
        if(!(S>>u & 1))
    {
        res = min(res, dfs(S|1<<u, u)+d[v][u]);
    }
    return dp[S][v] = res;
}

int main()
{
    int m;
    while(~scanf("%d%d", &n, &m))
    {
        int u, v, w;
        for(int i=0; i<maxn; i++)
            for(int j=0; j<maxn; j++)
            d[i][j] = INF;

        memset(dp, -1, sizeof(dp));
        for(int i=0; i<m; i++)
            {
                scanf("%d%d%d", &u, &v, &w);
                d[u][v] = w;
            }
        cout<<dfs(0, 0)<<endl;
    }
    return 0;
}

/*

5 8
4 0 7
4 1 6
3 4 3
2 3 5
2 0 4
1 2 5
0 3 4
0 1 3

*/