状压DP——2800 送外卖

2800 送外卖

题目链接

利用状压DP，其可以走多次用Floyd

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<iomanip>


#define INF 0x3f3f3f3f
using namespace std;
typedef  long long ll;
const int MOD  = 100000007;
const int N = 16;

int dp[N][1<<N];

int n;
int mm[N+2][N+2];

void floyd()
{
    for(int k = 0 ; k < n;k++)
    {
        for(int j = 0 ;j < n;j++)
        {
            for(int i = 0;i < n;i++)
            {
                mm[i][j] = min(mm[i][j] , mm[i][k]+mm[k][j]);
            }
        }

    }
}




int main() {
     ios_base::sync_with_stdio(false);
//    freopen("data.txt","r",stdin);

    while(cin >> n)
    {
        memset(dp,INF,sizeof(dp));
        n++;
        for(int i =0 ;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                cin >> mm[i][j];
            }
        }

        floyd();
        dp[0][0]=0;
        for(int stat = 0 ; stat < (1<<n); stat++)
        {
            for(int i = 0;i < n;i++)
            {
                if(dp[i][stat]==INF) continue;
                for(int j= 0;j<n;j++)
                {
                    if(stat&(1<<j))
                        continue;

                    int nex = stat|(1<<j);

                    dp[j][nex] = min(dp[j][nex] , dp[i][stat] + mm[i][j] );

                }
            }
        }

        cout <<dp[0][(1<<n)-1] <<endl;

    }
    return 0;
}