bzoj1003物流运输——DP

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=1003

DP好题；

直接找一个时间段的最短路，并用它来预处理出每个时间段的最小花费；

f[i]代表一条路走到时间的花费，所以转移要加上K。

枚举所有路线的TLE代码：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int n,m,K,e,head[],ct,D,d[],rt[],pr[],f[][],cnt,ans;

bool vis[];

struct N{

    int to,next,w;

    N(int t=,int n=,int w=):to(t),next(n),w(w) {}

}edge[];

void dfs(int x,int r,int p)

{

    if(x==m)

    {

        rt[++cnt]=(r|(<<(m-)));

        pr[cnt]=p;

        return;

    }

    vis[x]=;

    for(int i=head[x];i;i=edge[i].next)

    {

        int v=edge[i].to;

        if(vis[v])continue;

        dfs(v,(r|(<<(v-))),p+edge[i].w);

    }

    vis[x]=;

}

int main()

{

    scanf("%d%d%d%d",&n,&m,&K,&e);

    for(int i=,x,y,z;i<=e;i++)

    {

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

        edge[++ct]=N(y,head[x],z);head[x]=ct;

        edge[++ct]=N(x,head[y],z);head[y]=ct;

    }

    scanf("%d",&D);

    for(int i=,p,a,b;i<=D;i++)

    {

        scanf("%d%d%d",&p,&a,&b);

        for(int j=a;j<=b;j++)d[j]|=(<<(p-));//第j天不能通过的码头

    }

    dfs(,,);

    memset(f,0x3f,sizeof f);

    for(int j=;j<=cnt;j++)f[][j]=;

    for(int i=;i<=n;i++)

        for(int j=;j<=cnt;j++)

        {

            if(rt[j]&d[i])continue;

            for(int k=;k<=cnt;k++)

                f[i][j]=min(f[i][j],f[i-][k]+(j==k?pr[j]:K+pr[j]));

        }

    ans=0x3f;

    for(int j=;j<=cnt;j++)ans=min(ans,f[n][j]);

    printf("%d",ans);

    return ;

}

囧

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

queue<int>q;

int const inf=0x3f3f3f3f;

int n,m,K,e,head[],ct,mr[][],D,zt[],dis[],f[];

bool vis[],d[][];

struct N{

    int to,next,w;

    N(int t=,int n=,int w=):to(t),next(n),w(w) {}

}edge[];

void spfa()

{

    memset(vis,,sizeof vis);

    memset(dis,0x3f,sizeof dis);

    while(q.size())q.pop();

    dis[]=;q.push();vis[]=;

    while(q.size())

    {

        int x=q.front();q.pop();vis[x]=;

        for(int i=head[x];i;i=edge[i].next)

        {

            int v=edge[i].to;

            if(dis[v]>dis[x]+edge[i].w&&!zt[v])

            {

                dis[v]=dis[x]+edge[i].w;

                if(!vis[v])vis[v]=,q.push(v);

            }

        }

    }

}

int main()

{

    scanf("%d%d%d%d",&n,&m,&K,&e);

    for(int i=,x,y,z;i<=e;i++)

    {

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

        edge[++ct]=N(y,head[x],z);head[x]=ct;

        edge[++ct]=N(x,head[y],z);head[y]=ct;

    }

    scanf("%d",&D);

    for(int i=,p,a,b;i<=D;i++)

    {

        scanf("%d%d%d",&p,&a,&b);

        for(int j=a;j<=b;j++)d[p][j]=;

    }

    for(int i=;i<=n;i++)

    {

        memset(zt,,sizeof zt);

        for(int j=i;j<=n;j++)

        {

            for(int k=;k<=m;k++)zt[k]|=d[k][j];

            spfa();

            mr[i][j]=dis[m];//在下面乘 小心爆int

        }

    }

    for (int i=;i<=n;i++)

        for (int j=i;j<=n;j++)

            if (mr[i][j]<inf)mr[i][j]*=(j-i+);

    for(int i=;i<=n;i++)f[i]=mr[][i];

    for(int i=;i<=n;i++)

    {

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

            f[i]=min(f[i],f[j]+mr[j+][i]+K);

    }

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

    return ;

}