洛谷 P1772 【ZJOI2006】物流运输 题解

洛谷 P1772 【ZJOI2006】物流运输 题解

xiaoh 2020-7-23

题意

有$n$天，$m$个点构成一张无向图，有一些点在一些时候不可用，我们需要将物资从$1$号点运输到$m$号点，更换一次线路的代价为$k$，求$n$天的最小代价。

数据范围

$1\leq n\leq 100,1\leq m\leq 20,边权没有给，大致\leq 10^7$

题解

首先考虑进行$dp$。记$f_i$为前$i$天完成运输的最小代价。那么得到转移方程：

$f_i=[1\leq j<i]\;f_j+dis(j+1,i)\times (i-j)+k$

其中$dis(j+1,i)$表示从第$j+1$天到第$i$天采用同一个相同的线路能够达到的最小代价。由于采用的相同线路，因而任何一天被封禁的道路都不了用，然后直接用$Floyd$即可。时间复杂度$O(n^2m^3)$。

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
const int MAXN=110,MAXM=22;
const int inf=999999;
int n,m,k,e,d;
int mp[MAXM][MAXM];
bool book[MAXM][MAXN];
int f[MAXN];
inline int dis(int l,int r)
{
    int dis[MAXM][MAXM];
    bool flag[MAXM];
    memset(flag,1,sizeof(flag));
    for(int i=1;i<=m;++i)
    for(int j=l;j<=r;++j)
    if(!book[i][j])
    {
        flag[i]=0;
        break;
    }
    for(int i=1;i<=m;++i)
    for(int j=1;j<=m;++j) dis[i][j]=mp[i][j];
    for(int k=1;k<=m;++k)
    if(flag[k])
    for(int i=1;i<=m;++i)
    if(flag[i])
    for(int j=1;j<=m;++j)
    if(flag[j]) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
    return dis[1][m];
}
int main()
{
    read(n),read(m),read(k),read(e);
    for(int i=1;i<=m;++i)
    for(int j=1;j<=m;++j) mp[i][j]=(i==j)? 0:inf;
    for(int i=1;i<=e;++i)
    {
        int x,y,c;
        read(x),read(y),read(c);
        mp[x][y]=mp[y][x]=min(mp[x][y],c);
    }
    read(d);
    memset(book,1,sizeof(book));
    for(int i=1;i<=d;++i)
    {
        int p,a,b;
        read(p),read(a),read(b);
        for(int j=a;j<=b;++j) book[p][j]=0;
    }
    for(int i=1;i<=n;++i) f[i]=dis(1,i)*i;
    for(int i=1;i<=n;++i)
    for(int j=1;j<i;++j) f[i]=min(f[i],f[j]+dis(j+1,i)*(i-j)+k);
    write(f[n]),putchar('\n');
	return 0;
}