[BZOJ1003/Luogu1772][ZJOI2006]物流运输(最短路径,动态规划)

发布于 2018-02-03  80 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1003/Luogu1772][ZJOI2006]物流运输(最短路径,动态规划)

Description

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

Http

BZOJ
Luogu

Tag

最短路径,动态规划

解决思路

看到数据范围,我们可以预处理出\(Cost[i][j]\)表示从第\(i\)天到第\(j\)天每一天的最短花费,这个直接求最短路即可。
接下来动态转移,设\(F[i]\)表示前\(i\)天的最小花费,那么枚举前面的某一天转移即可。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxDay=110;
const int maxN=21;
const int maxM=maxN*maxN*2;
const int maxQueue=maxN*1000;
const int inf=21474836;

int Day,n,m,K;
int Cant[maxDay];
int edgecnt=0,Head[maxN],Next[maxM],V[maxM],W[maxM];
int Cost[maxDay][maxDay];
int Queue[maxQueue],Dist[maxN];
bool inqueue[maxN];
int F[maxDay];

void Add_Edge(int u,int v,int w);
void _Add(int u,int v,int w);
int Spfa(int l,int r);

int main()
{
    mem(Head,-1);
    scanf("%d%d%d%d",&Day,&n,&K,&m);
    for (int i=1;i<=m;i++)
    {
        int u,v,w;scanf("%d%d%d",&u,&v,&w);u--;v--;
        Add_Edge(u,v,w);
    }
    int d;scanf("%d",&d);
    for (int i=1;i<=d;i++)
    {
        int P,l,r;scanf("%d%d%d",&P,&l,&r);
        P--;
        for (int j=l;j<=r;j++) Cant[j]|=(1<<P);
    }
    for (int i=1;i<=Day;i++)
        for (int j=i;j<=Day;j++)
            Cost[i][j]=Spfa(i,j);
    mem(F,63);F[0]=0;
    for (int i=1;i<=Day;i++)
    {
        F[i]=Cost[1][i]*i;
        for (int j=0;j<i;j++)
            F[i]=min(F[i],F[j]+(i-j)*Cost[j+1][i]+K);
    }
    printf("%d\n",F[Day]);
    return 0;
}

void Add_Edge(int u,int v,int w)
{
    _Add(u,v,w);_Add(v,u,w);
    return;
}

void _Add(int u,int v,int w)
{
    edgecnt++;Next[edgecnt]=Head[u];Head[u]=edgecnt;V[edgecnt]=v;W[edgecnt]=w;
    return;
}

int Spfa(int l,int r)
{
    int cant=0;
    for (int i=l;i<=r;i++) cant|=Cant[i];
    mem(Dist,-1);Dist[0]=0;
    int h=1,t=0;Queue[1]=0;
    do
    {
        t++;if (t==maxQueue) t=0;
        int u=Queue[t];
        for (int i=Head[u];i!=-1;i=Next[i])
            if (((1<<V[i])&cant)==0)
                if ((Dist[V[i]]==-1)||(Dist[u]+W[i]<Dist[V[i]]))
                {
                    Dist[V[i]]=Dist[u]+W[i];
                    if (inqueue[V[i]]==0)
                    {
                        h++;if (h==maxQueue) h=0;
                        inqueue[Queue[h]=V[i]]=1;
                    }
                }
        inqueue[u]=0;
    }
    while (t!=h);
    if (Dist[n-1]==-1) return inf;
    return Dist[n-1];
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1003/Luogu1772][ZJOI2006]物流运输(最短路径,动态规划)


HNCJ OIer