[ZJOI2006]物流运输

[ZJOI2006]物流运输

分析

1. 方法一：这是我一开始想到的一种方法。我可以先预处理出所有的可行路径，因为m范围较小。一个dfs深搜过去，加一个状态压缩，就能得到路径上所有的节点以及路径的花费。剩下的就是dp的事情了。选出每一天的可行路径，然后枚举前一天走的路径。似乎是2^18*2^18，复杂度略大，可以优化一下。代码没来得及码。。。

2. 方法二：这是小菜鸡发现自己的状压要爆炸，于是点开题解开始厚颜无耻学习的结果。主要是要通过spfa预处理出一个co [ i ] [ j ] : 第 i 天到第 j 天走的最短路长度，然后就可以直接dp了

代码(方法二)

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int N=110,M=22;

int n,m,k,e,tot;
int h[M],nex[N<<2],ver[N<<2],pri[N<<2];
int sum[M],bl[2][M][N],dis[N];
ll f[N],co[N][N];
bool vis[M];

inline void add(int x,int y,int z)
{
    nex[tot]=h[x];
    ver[tot]=y;
    pri[tot]=z;
    h[x]=tot++;
}

inline bool check(int now,int l,int r)
{
    for (int i=1;i<=sum[now];i++)
        if(!(bl[0][now][i]>r||bl[1][now][i]<l))
            return 1;

    return 0;
}

inline int bfs(int x,int y)
{
    memset(vis,0,sizeof(vis));
    memset(dis,0x3f,sizeof(dis));
    queue<int>q;
    dis[1]=0;
    q.push(1);
    while(!q.empty())
    {
        int k=q.front();q.pop();
        vis[k]=0;
        for (int i=h[k];~i;i=nex[i])
        {
            int j=ver[i];
            if(check(j,x,y)) continue;
            if(dis[j]>dis[k]+pri[i])
            {
                dis[j]=dis[k]+pri[i];
                if(!vis[j]) vis[j]=1,q.push(j);
            }
        }
    }

    return dis[m];
}

int main()
{
    memset(h,-1,sizeof(h));

    scanf("%d%d%d%d",&n,&m,&k,&e);
    for (int i=1;i<=e;i++)
    {
        int x,y,z;scanf("%d%d%d",&x,&y,&z);
        add(x,y,z),add(y,x,z);
    }
    int d;scanf("%d",&d);
    while(d--)
    {
        int p,a,b;scanf("%d%d%d",&p,&a,&b);
        ++sum[p];
        bl[0][p][sum[p]]=a;
        bl[1][p][sum[p]]=b;
    }

    for (int i=1;i<=n;i++)
        for (int j=i;j<=n;j++)
            co[i][j]=bfs(i,j);

    for (int i=1;i<=n;i++) f[i]=i*co[1][i];

    for (int i=2;i<=n;i++)    
        for (int j=1;j<i;j++)
            f[i]=min(f[i],f[j]+(i-j)*co[j+1][i]+k);

    printf("%lld\n",f[n]);

    return 0;
}