洛谷P1772 [ZJOI2006]物流运输 题解

题目链接：P1772 [ZJOI2006]物流运输

题意：物流公司要把一批货物从码头 A 运到码头 B。由于货物量比较大，需要 $n$ 天才能运完。货物运输过程中一般要转停好几个码头。

物流公司通常会设计一条固定的运输路线，以便对整个运输过程实施严格的管理和跟踪。由于各种因素的存在，有的时候某个码头会无法装卸货物。这时候就必须修改运输路线，让货物能够按时到达目的地。

但是修改路线是一件十分麻烦的事情，会带来额外的成本。因此物流公司希望能够订一个 $n$ 天的运输计划，使得总成本尽可能地小。

输入格式

第一行是四个整数 $n,m,k,e$ 。$n$ 表示货物运输所需天数，$m$ 表示码头总数，$k$ 表示每次修改运输路线所需成本，$e$ 表示航线条数。

接下来 $e$ 行每行是一条航线描述，包括了三个整数，依次表示航线连接的两个码头编号以及航线长度。其中码头 A 编号为 $1$ ，码头 B 编号为 $m$ 。单位长度的运输费用为 $1$。航线是双向的。

再接下来一行是一个整数 $d$，后面的 $d$ 行每行是三个整数 $p,a,b$。表示编号为 $p$ 的码头在 $[a,b]$ 天之内无法装卸货物。同一个码头有可能在多个时间段内不可用。但任何时间都存在至少一条从码头 A 到码头 B 的运输路线。

输出格式

包括了一个整数表示最小的总成本。
总成本为 $n$ 天运输路线长度之和 $+k\times$改变运输路线的次数。

输入输出样例

输入 #1

5 5 10 8
1 2 1
1 3 3
1 4 2
2 3 2
2 4 4
3 4 1
3 5 2
4 5 2
4
2 2 3
3 1 1
3 3 3
4 4 5

输出 #1

32

说明/提示

【数据范围】 对于 $100\%$ 的数据，$1 \le n \le 100$，$1\le m \le 20$。

【样例输入说明】

上图依次表示第 $1$ 至第 $5$ 天的情况，阴影表示不可用的码头。

【样例输出说明】

前三天走 $1 \to 4 \to 5$，后两天走 $1 \to 3 \to 5$，这样总成本为 $(2+2)\times 3+(3+2)\times 2+10=32$ 。

先不考虑图的问题

令 $s[i][j]$ 为第 $i$ 天到第 $j$ 天不换路的最小花费

设 $dp[i]$ 为前 $i$ 天的最小花费

则有

$$dp[i]=\min_{1\le j\le i}(dp[i],dp[j-1]+s[i][j]\times(i-j+1)+k)$$

即前 $j-1$ 天都不改变路线，第 $j$ 天到第 $i$ 天走同一条路线

那么直接dp就完了

现在问题是怎么求出 $s[i][j]$

因为要求最小花费，那么一定是这几天都可以走的结点所成的最短路的花费 $\times$ 天数（ $i-j+1$ ）

直接暴力跑dijkstra就好了

时间复杂度 $O(n^3m)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x1f1f1f1f1f1f1f1f
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N (int)(1e3+15)
struct Edge
{
    int u,v,w,next;
}e[N];
int n,m,k,E,d;
bool c[N][N],vis[N];
int pos=1,head[N],s[N][N],dis[N],dp[N];
void addEdge(int u,int v,int w)
{
    e[++pos]={u,v,w,head[u]};
    head[u]=pos;
}
struct node{int u,dis;};
bool operator<(node a,node b){return a.dis>b.dis;}
priority_queue<node> q;
int mul(int a,int b)
{
    return a==INF?INF:a*b;
}
void dijkstra(int st)
{
    memset(dis,0x1f,sizeof(dis));
    while(!q.empty())q.pop();
    q.push({st,dis[st]=0});
    while(!q.empty())
    {
        int u=q.top().u;q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(int i=head[u]; i; i=e[i].next)
        {
            int v=e[i].v,w=e[i].w;
            if(dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                q.push({v,dis[v]});
            }
        }
    }
}
signed main()
{
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    read(n);read(m);read(k);read(E);
    for(int i=1,u,v,w; i<=E; i++)
    {
        read(u);read(v);read(w);
        addEdge(u,v,w);addEdge(v,u,w);
    }
    read(d);
    for(int i=1,p,l,r; i<=d; i++)
    {
        read(p);read(l);read(r);
        for(int j=l; j<=r; j++)
            c[p][j]=1;
    }
    for(int i=1; i<=n; i++)
        for(int j=i; j<=n; j++)
        {
            memset(vis,0,sizeof(vis));
            for(int a=1; a<=m; a++)
                for(int b=i; b<=j; b++)
                    if(c[a][b])vis[a]=1;
            dijkstra(1);
            s[i][j]=dis[m];
        }
    memset(dp,0x1f,sizeof(dp));
    for(int i=1; i<=n; i++)
    {
        dp[i]=mul(s[1][i],i);
        for(int j=i; j>=1; j--)
            dp[i]=min(dp[i],dp[j-1]+mul(s[j][i],(i-j+1))+k);
    }
    printf("%lld\n",dp[n]);
    return 0;
}