洛谷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;
}