BZOJ_1003_[ZJOI2006]物流运输_最短路+dp

BZOJ_1003_[ZJOI2006]物流运输_最短路+dp

题意：http://www.lydsy.com/JudgeOnline/problem.php?id=1003

分析：

这种一段一段的显然要用dp求。

f[i]表示到第i天为止的最小花销。转移有f[i]=min{f[j-1]+cost[j][i]*(i-j+1)+k};

其中cost[i][j]表示从i到j天的最短路长度，spfa预处理出来。

代码：

#include <stdio.h>

#include <string.h>

#include <algorithm>

using namespace std;

int head[30],to[1000],nxt[1000],val[1000],cnt;

int n,m,k,t,inb[110][30],f[110],cost[110][110],can[30];

int Q[100],l,r,dis[30],inq[30];

inline void add(int u,int v,int w){

    to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;val[cnt]=w;

}

int spfa(int be,int en){

    for(int i=1;i<=n;i++)can[i]=0;

    for(int i=be;i<=en;i++)

        for(int j=1;j<=n;j++)if(inb[i][j])

            can[j]=1;

    l=r=0;

    memset(dis,0x3f,sizeof(dis));

    dis[1]=0;Q[r++]=1;inq[1]=1;

    while(l^r){

        int x=Q[l++];if(l==n+10)l=0;inq[x]=0;

        for(int i=head[x];i;i=nxt[i]){

            if(can[to[i]])continue;

            if(dis[to[i]]>dis[x]+val[i]){

                dis[to[i]]=dis[x]+val[i];

                if(!inq[to[i]]){

                    inq[to[i]]=1;Q[r++]=to[i];if(r==n+10)r=0;

                }

            }

        }

    }

    return dis[n]>100000?-1:dis[n];

}

int main(){

    scanf("%d%d%d%d",&t,&n,&k,&m);

    int x,y,z;

    for(int i=1;i<=m;i++){

        scanf("%d%d%d",&x,&y,&z);

        add(x,y,z);add(y,x,z);

    }

    int h;

    scanf("%d",&h);

    for(int i=1;i<=h;i++){

        scanf("%d%d%d",&x,&y,&z);

        if(y>z)swap(y,z);

        for(int j=y;j<=z;j++)inb[j][x]=1;

    }

    for(int i=1;i<=t;i++){

        for(int j=i;j<=t;j++){

            cost[i][j]=spfa(i,j);

            //printf("%d\n",cost[i][j]);

        }

    }

    f[0]=0;

    for(int i=1;i<=t;i++){

        f[i]=1<<30;

        for(int j=1;j<=i;j++){

            if(cost[j][i]==-1)continue;

            f[i]=min(f[j-1]+cost[j][i]*(i-j+1)+k,f[i]);

        }

        //printf("%d\n",f[i]);

    }

    printf("%d",f[t]-k);

}

BZOJ_1003_[ZJOI2006]物流运输_最短路+dp的相关教程结束。