[ZJOI2006]物流运输(状压写法)

m这么小,不用状压也太扯淡了

我们发现有价值的是每条路线上的经过的点集合

定义为第天点,目前走集合为的路线的最小花费

那么使用爆搜出所有路线(当然要剪枝),记录对应状态和花费

发现数组的第一维可以滚动数组变成

又因为每条路线都有点,所以可以去掉变成

就是枚举当前第天的路线,再枚举上一天的路线,这样是的

其实上一天我们只需要最小值就好了,所以过程中就可以取最小值

跑起来也很快

#include <bits/stdc++.h>
using namespace std;
const int maxn=209;
int f[1<<19],vis[209],isok[209],ju[1<<18],dp[2][1<<18];
int n,m,k,e;
struct p{
    int to,nxt,w;
}d[maxn*maxn]; int head[maxn*maxn],cnt=1;
void add(int u,int v,int w){ d[cnt]=(p){v,head[u],w},head[u]=cnt++; }
void dfs(int u,int state,int dis)
{
    if( dis>=f[state] )    return;
    f[state]=dis;
    if( u==m )
    {
        state^=(1<<(m-2));
        ju[state] = min( ju[state],dis ); return;
    }
    for(int i=head[u];i;i=d[i].nxt )
    {
        int v=d[i].to; if( vis[v] )    continue;
        vis[v]=1; 
        dfs(v,state|(1<<(v-2)),dis+d[i].w );
        vis[v]=0;
    }
}
int main()
{
    cin >> n >> m >> k >> e;
    memset(ju,0x3f,sizeof(ju));
    memset(f,0x3f,sizeof(f));        
    for(int i=1;i<=e;i++)
    {
        int l,r,w; cin >> l >> r >> w;
        add(l,r,w); add(r,l,w);
    }
    cin >> e;
    for(int i=1;i<=e;i++)
    {
        int id,l,r; cin >> id >> l >> r;
        for(int j=l;j<=r;j++)    isok[j]|=(1<<(id-2));
    }
    vis[1]=1;
    dfs(1,0,0);
    int last=0;
    for(int i=1;i<=n;i++)
    {
        int temp=1e9,t=(i&1);
        for(int j=0;j<(1<<(m-2));j++)
        {
            if( ju[j]==1e9 )    { dp[t][j]=1e9; continue; }
            if( isok[i]&j )    { dp[t][j]=1e9; continue; }
            dp[t][j]=min( dp[t^1][j]+ju[j],last+k+ju[j] );
            temp = min( temp,dp[t][j] ); 
        }
        last=temp;
    }
    cout << last;
}