BZOJ-1003: [ZJOI2006]物流运输

[文章目录]

Description

物流公司要把一批货物从码头A运到码头B。由于货物量比较大,需要n天才能运完。货物运输过程中一般要转停m个码头中的几个。物流公司通常会设计一条固定的运输路线,以便对整个运输过程实施严格的管理和跟踪。由于各种因素的存在,有的时候某个码头会无法装卸货物。这时候就必须修改运输路线,让货物能够按时到达目的地。但是修改路线是一件十分麻烦的事情,会带来额外的成本。因此物流公司希望能够订一个n天的运输计划,使得总成本尽可能地小。n<=100 m<=20

预处理每个时间段从始至终码头都可用的状态下的最短路,之后区间DP即可。时间复杂度O(n^2*spfa)。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int n,m,K,e,d,mp[25][25];
int q[500],dis[25],ex[110];
ll f[110][110],dp[110];
bool vis[25];
int spfa()
{
    memset(dis,0x3f,sizeof dis);
    dis[1]=0; q[1]=1; int i,x,l=1,r=1;
    while(l<=r)
    {
        x=q[l++]; vis[x]=0;
        for(i=1;i<=m;++i) if(dis[x]+mp[x][i]<dis[i])
        {
            dis[i]=dis[x]+mp[x][i];
            if(!vis[i]) q[++r]=i,vis[i]=1;
        }
    }
    return dis[m];
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&K,&e);
    int i,j,k,x,y,z;
    memset(mp,0x3f,sizeof mp);
    for(i=1;i<=e;++i)
    {
        scanf("%d%d%d",&x,&y,&z);
        if(z<mp[x][y]) mp[x][y]=mp[y][x]=z;
    }
    scanf("%d",&d);
    for(i=1;i<=d;++i)
    {
        scanf("%d%d%d",&x,&y,&z);
        while(y<=z) ex[y]|=1<<(x-1),++y;
    }
    for(i=1;i<=n;++i)
    {
        x=0;
        for(j=i;j<=n;++j)
        {
            x|=ex[j];
            for(k=0;k<m;++k) vis[k+1]=(x>>k)&1;
            f[i][j]=spfa();
        }
    }
    for(i=1;i<=n;++i)
    {
        dp[i]=f[1][i]*i;
        for(j=2;j<=i;++j)
            dp[i]=min(dp[i],dp[j-1]+f[j][i]*(i-j+1)+K);
    }
    printf("%lld",dp[n]);
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注