物流运输(最短路+dp)

这道题是相当的火，但是在tyher的讲解下我一遍就AC了！！！

Part 1 理解题目

从第一天到最后一天，总会有一些点莫名其妙地走不了，所以导致我们不能按照上一次的最短路一直运输得到最少费用，而需要不停地更换航线来保证可以运到终点，答案就是在这些方案中选出运输费用最少的。

Part 2 思想过程

首先会想到我们每天都跑一遍SPFA，找最短路，如果和上一天不一样，那就改航线，加一下K的贪心方法。这样显然是错误的伪得不能再伪的贪心，而且要把最短路一个一个抠出来，不说T，写都写死你！

然后我们发现，这道题每天无非就两种决策，一种换航线，一种不换航线。那么，就可以想到dp(至于怎么想到的……题解帮我想的）我们设dp[i]表示前i天航行送完所有的货物所需要的最小花费。转移：dp[i]=min(dp[i],dp[j]+K+w[j+1][i]);这里的j是枚举的i之前的第几天，w[i][j]是从i天到j天航线都可以走的最短路，K是换航线的费用。既然出现了“最短路”这种东西，那就SPFA吧，把这期间不能走的点标记一下，跑一遍裸的SPFA，再记入数组，算一个王者预处理吧……哈哈哈……

Part 3 代码实现

dp过程

 for(rg int i=;i<=day;++i)

 {

     dp[i]=w[][i];

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

     {

         p[i]=min(dp[i],dp[j]+K+w[j+][i]);

     }

 }

SPFA之前的处理码头

读入损坏码头

 for(rg int i=;i<=d;++i)

 {

     rg int p=read(),a=read(),b=read();

     for(rg int j=a;j<=b;++j)

     　　bre[j][++bre[j][]]=p;

 }

标记损坏码头(每一次枚举到的时间区间都要做)

memset(b,,sizeof(b));

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

{

    for(rg int l=;l<=bre[k][];l++)

    {

        b[bre[k][l]]=;

    }

}

SPFA模板

inline void SPFA()

{

    memset(vis,,sizeof(vis));

    memset(team,,sizeof(team));

    for(rg int i=;i<=n;++i)dis[i]=;

    rg int top=,tail=;

    team[]=;vis[]=;dis[]=;

    while(top<tail)

    {

        top++;

        rg int now=team[top];vis[now]=;

        for(rg int i=head[now];i;i=ljl[i].nxt)

        {

            rg int qw=ljl[i].to;

            if(dis[qw]>dis[now]+ljl[i].v&&!b[qw])

            {

                dis[qw]=dis[now]+ljl[i].v;

                if(!vis[qw])

                {

                    team[++tail]=qw;

                    vis[qw]=;

                }

            }

        }

    }

}

完整代码！！！

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<iomanip>

#include<algorithm>

#include<ctime>

#include<queue>

#define rg register

#define lst long long

#define N 150

#define M 1200

using namespace std;

int day,n,K,m,d,cnt;

struct edge{

    int to,v,nxt;

}ljl[M<<];

int head[N],team[N],dis[N],dp[N];

int w[N][N],bre[N][N];

bool vis[N],b[N];

inline int read()

{

    rg int s=,m=;rg char ch=getchar();

    while(ch!='-'&&(ch<''||ch>''))ch=getchar();

    if(ch=='-')m=-,ch=getchar();

    while(ch>=''&&ch<='')s=(s<<)+(s<<)+ch-'',ch=getchar();

    return s*m;

}

inline void add(rg int p,rg int q,rg int o)

{

    ljl[++cnt].to=q;

    ljl[cnt].v=o;

    ljl[cnt].nxt=head[p];

    head[p]=cnt;

}

inline void SPFA()

{

    memset(vis,,sizeof(vis));

    memset(team,,sizeof(team));

    for(rg int i=;i<=n;++i)dis[i]=;

    rg int top=,tail=;

    team[]=;vis[]=;dis[]=;

    while(top<tail)

    {

        top++;

        rg int now=team[top];vis[now]=;

        for(rg int i=head[now];i;i=ljl[i].nxt)

        {

            rg int qw=ljl[i].to;

            if(dis[qw]>dis[now]+ljl[i].v&&!b[qw])

            {

                dis[qw]=dis[now]+ljl[i].v;

                if(!vis[qw])

                {

                    team[++tail]=qw;

                    vis[qw]=;

                }

            }

        }

    }

}

int main()

{

    day=read(),n=read(),K=read(),m=read();

    for(rg int i=;i<=m;++i)

    {

        rg int p=read(),q=read(),o=read();

        add(p,q,o),add(q,p,o);

    }

    d=read();

    for(rg int i=;i<=d;++i)

    {

        rg int p=read(),a=read(),b=read();

        for(rg int j=a;j<=b;++j)

            bre[j][++bre[j][]]=p;

    }

    for(rg int i=;i<=day;++i)

    {

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

        {

            memset(b,,sizeof(b));

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

            {

                for(rg int l=;l<=bre[k][];l++)

                {

                    b[bre[k][l]]=;

                }

            }

            SPFA();

            if(dis[n]!=)w[i][j]=(j-i+)*dis[n];

            else w[i][j]=dis[n];

        }

    }

    for(rg int i=;i<=day;++i)

    {

        dp[i]=w[][i];

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

        {

            dp[i]=min(dp[i],dp[j]+K+w[j+][i]);

        }

    }

    cout<<dp[day]<<endl;

    return ;

}

巴特西

物流运输(最短路+dp)

最新文章

热门文章