送外卖状压DP

题目描述 Description

有一个送外卖的，他手上有n份订单，他要把n份东西，分别送达n个不同的客户的手上。n个不同的客户分别在1~n个编号的城市中。送外卖的从0号城市出发，然后n个城市都要走一次（一个城市可以走多次），最后还要回到0点（他的单位），请问最短时间是多少。现在已知任意两个城市的直接通路的时间。

输入描述 Input Description

输入文件meal.in的第一行一个正整数n （1<=n<=15）

接下来是一个（n+1）*(n+1)的矩阵，矩阵中的数均为不超过10000的正整数。矩阵的i行j列表示第i-1号城市和j-1号城市之间直接通路的时间。当然城市a到城市b的直接通路时间和城市b到城市a的直接通路时间不一定相同，也就是说道路都是单向的。

输出描述 Output Description

输出文件meal.out仅有一个正整数表示最少花费的时间

样例输入 Sample Input

0 1 10 10

1 0 1 2

10 1 0 10

10 2 10 0

样例输出 Sample Output

数据范围及提示 Data Size & Hint

50%的数据1 <= n <= 10

100%的数据1 <= n <= 15

和售货员的难题几乎没区别，就是首先floyd了一下。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define il inline
#define db double
#define replace(a , b) (a ^ (1 << b-1))
#define get(a , b) ((a >> b-1) & 1)
#define min(a , b) ((a) < (b) ? (a) : (b))
using namespace std;
il int gi()
{
    int x=0,y=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
        {
            if(ch=='-')
                y=-1;
            ch=getchar();
        }
    while(ch>='0'&&ch<='9')
        {
            x=x*10+ch-'0';
            ch=getchar();
        }
    return x*y;
}
int n,m,f[1<<21][21],r[21][21],ans=2e9,s;
int main()
{
    freopen("meal.in","r",stdin);
    freopen("meal.out","w",stdout);
    n=gi();n++;
    m=(1<<n)-1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            r[i][j]=gi();
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(r[i][j]>r[i][k]+r[k][j])
                    r[i][j]=r[i][k]+r[k][j];
    for(int i=1;i<=m;i+=2)
        for(int j=1;j<=n;j++)
            f[i][j]=2e9;
    f[1][1]=0;
    for(int i=3,k=2,p=4;i<=m;i+=2)
        {
            if(i>p)
                p=p<<1,k++;
            for(int j=2;j<=k;j++)
                {
                    if(get(i,j))
                        {
                            s=replace(i,j);
                            for(int l=1;l<j;l++)
                                f[i][j]=min(f[i][j],f[s][l]+r[l][j]);
                            for(int l=j+1;l<=k;l++)
                                f[i][j]=min(f[i][j],f[s][l]+r[l][j]);
                        }
                }
        }
    for(int i=2;i<=n;i++)
        ans=min(ans,f[m][i]+r[i][1]);
    printf("%d
",ans);
    return 0;
}

PEACE

送外卖 状压DP

送外卖状压DP