题解：P1772 [ZJOI2006] 物流运输

· · 题解

更优秀的状压做法。

看到题解区只有一个用状压的，还用了 dfs，于是发一篇只用状压的题解。

首先发现点数只有 20，下意识状压。于是直接用二进制数表示路径，i 位为 1 代表经过第 i 个点。

预处理出 dis 数组，dis_i 表示路径为 i 时的最短路。

设 f_{i,j} 表示第 i 天当前路径为 j 的最小花费。然后就可以枚举天数转移了。将这天不合法的路径花费设为正无穷，其余有两种转移。可以选择路径不变，那么花费加上 dis_i 也可以从其他路径改变过来，花费为 min\{f_j|j\not= i\}+dis_i+k。

难点在于预处理，直接 dfs 会 TLE。于是用 dd_{i,j} 表示 j 点与 i 中点最近的距离。先状压 dp 预处理出 dd 数组，然后就可以愉快地状压 dp 出 dis 数组了。

code

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n,m,k,e;
bool c[N];
int dis[1<<20],dd[1<<20][20];
int f[1<<20],mi;
int cnt[N];
vector<int> ad[N],ea[N];
signed main()
{
    cin>>n>>m>>k>>e;
    int x,y,d;
    memset(dis,0x3f,sizeof dis);
    memset(dd,0x3f,sizeof dd);
    for(int i=1;i<=e;i++)
    {
        cin>>x>>y>>d;
        dd[1<<(x-1)][y-1]=min(dd[1<<(x-1)][y-1],d);
        dd[1<<(y-1)][x-1]=min(dd[1<<(y-1)][x-1],d);
    }
    for(int i=0;i<m;i++)
    {
        dd[1<<i][i]=0;
    }
    int tmp;
    for(int i=0;i<(1<<m);i++)
    {
        for(int j=0;j<m;j++)
        {
            tmp=i&-i;
            dd[i][j]=min(dd[i^tmp][j],dd[tmp][j]);
        }
    }
    dis[1]=0;
    for(int i=0;i<(1<<m);i++)
    {
        if(!(i&1))continue;
        for(int j=0;j<m;j++)
        {
            if(!(i&(1<<j)))continue;
            dis[i]=min(dis[i],dis[i^(1<<j)]+dd[i^(1<<j)][j]);
        }
    }
    int l,r,p;
    cin>>d;
    for(int i=1;i<=d;i++)
    {
        cin>>p>>l>>r;
        ad[l].push_back(p);
        ea[r+1].push_back(p);
    }
    for(int i=1;i<=n;i++)
    {
        int mii=1e9;
        tmp=0;
        for(auto j:ad[i])cnt[j]++;
        for(auto j:ea[i])cnt[j]--;
        for(int j=1;j<=m;j++)
        {
            if(cnt[j])
            {
                tmp|=1<<(j-1);
            }
        }
        for(int j=0;j<(1<<m);j++)
        {
            if((!(j&1))||(!(j&(1<<(m-1)))))continue;
            if(j&tmp)
            {
                f[j]=1e9+7;
                continue;
            }
            f[j]=min(f[j]+dis[j],mi+k+dis[j]);
            mii=min(mii,f[j]);
        }
        mi=mii;
    }
    int ans=1e9;
    for(int i=0;i<(1<<m);i++)
    {
        if((!(i&1))||(!(i&(1<<(m-1)))))continue;
        ans=min(ans,f[i]);
    }
    cout<<ans;
}