题解 P1772 【[ZJOI2006]物流运输】

2018-07-08 18:24:45


spfa+dp。。。

难想的主要是dp部分,这里只用一维。用dp[i]表示第i天 所用的最小花费。如果用v[i][j]表示i~j天不改变路线的最小花费,则转移方程就是:dp[i]=min(dp[i],d[j]+v[j+1][i]+k)

那么问题就是怎么求v。很简单,枚举一下i和j,直接暴力用spfa求。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,k,e,d,cnt=0,ans=0;
int head[200000],nxt[200000],to[200000],val[200000];
int f[50][110],h[100],dis[100],q[10000],v[110][110];
int dp[110];
void addedge(int x,int y,int z)
{
    cnt++;
    nxt[cnt]=head[x];
    head[x]=cnt;
    to[cnt]=y;
    val[cnt]=z;
}
int spfa(int x,int y)
{
    memset(h,0,sizeof(h));
    memset(dis,0x7f,sizeof(dis));
    int l=0,r=1;
    q[1]=1,dis[1]=0,h[1]=1;
    while(l<r)
    {
        int u=q[++l];
        for(int i=head[u];i!=-1;i=nxt[i])
        {
            int v=to[i];
            if(f[v][y]-f[v][x-1]) continue;//判断x-y天v码头是否会无法装载
            if(dis[v]>dis[u]+val[i])
            {
                dis[v]=dis[u]+val[i];
                if(!h[v])
                {
                    h[v]=1;
                    q[++r]=v;
                }
            }
        }
        h[u]=0;
    }
    return dis[m];
}
int main()
{
    memset(f,0,sizeof(f));
    memset(v,0x7f,sizeof(v));
    memset(dp,0x7f,sizeof(dp));
    memset(head,-1,sizeof(head));
    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);
        addedge(x,y,z);
        addedge(y,x,z);
    }
    scanf("%d",&d);
    for(int i=1;i<=d;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        for(int j=y;j<=z;j++)
            f[x][j]=1;
    }
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            f[i][j]+=f[i][j-1];//做前缀和,方便spfa时判断
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
            v[i][j]=spfa(i,j);
    dp[0]=0;
    for(int i=1;i<=n;i++)
        for(int j=0;j<i;j++)
        {
            if(v[j+1][i]==2139062143) continue;//如果i~j天没有不改变路线的方法就跳过,这个乱七八糟的值,时memset时候附上去的
            dp[i]=min(dp[j]+v[j+1][i]*(i-j)+k,dp[i]);
        }
    printf("%d",dp[n]-k);
    return 0;
}