题解 P1772 【[ZJOI2006]物流运输】

· · 题解

好久没写题解了，来水一波蓝题题解QWQ。

题目大意：一张无向图，某些点在一段时间段里无法经过，但是改变路径需要K的额外成本，问n天里保持AB两点联通需要的最小成本。

思路：这题一眼就是最短路，显然在最短路径上不存在新障碍时之前最短路答案必定最优，所以对于某一天的最优答案，只要比较昨天的最优答案和从之前某一天一直采取另一条最短路的成本加上额外成本K。

f[i]表示到第i天的最优解，由于后面的决策与前面没有关系，所以无后效性成立。

状态转移方程就很显然了：

f[i]=max(f[i],f[j]+(i-j)*l[i+1][j]+k)

其中L是i+1到j天的最短路。

那么处理一下每段时间的最短路，跑n^2/2遍SPFA就好啦。

上代码（估计上面都没人看QWQ）。

#include <bits/stdc++.h>
using namespace std;
inline int read()
{
    int X=0,w=0; char ch=0;
    while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
    while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}//快读请无视
struct Edge{
    int nxt,to,val;
}E[805];
int head[105],tot;
void add(int x,int y,int z){
    E[++tot].nxt=head[x];
    E[tot].to=y;
    E[tot].val=z;
    head[x]=tot;
}//邻接表存图，没什么好说的
int n,m,k,e,d;//m是点e是边，写的时候别搞懵了
int block[105][105];
queue<int> q;
int vis[105],dis[105],close[105];
long long f[105];
int l[105][105];
int spfa(int a,int b){
    memset(vis,0,sizeof(vis));
    memset(dis,0x3f,sizeof(dis));
    memset(close,0,sizeof(close));
    for(int i=1;i<m;i++){
        for(int j=a;j<=b;j++){
            if(block[i][j])close[i]=1;
        }
    }//判断点是否关闭
    q.push(1);
    vis[1]=1;
    dis[1]=0;
    while(!q.empty()){
        int now=q.front();
        q.pop();
        vis[now]=0;
        for(int i=head[now];i;i=E[i].nxt){
            int to=E[i].to;
            if(close[to])continue;
            if(dis[to]>dis[now]+E[i].val){
                dis[to]=dis[now]+E[i].val;
                if(!vis[to])q.push(to),vis[to]=1;
            }
        }
    }//经典SPFA
    return dis[m];
}
int main() {
    n=read(),m=read(),k=read(),e=read();
    for(int i=1;i<=e;i++){
        int x=read(),y=read(),z=read();
        add(x,y,z);
        add(y,x,z);
    }//双向边建图
    d=read();
    for(int i=1;i<=d;i++){
        int p=read(),a=read(),b=read();
        for(int j=a;j<=b;j++)block[p][j]=1;
    }//表示某个点某一天是否关闭
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            l[i][j]=spfa(i,j);
        }
    }//储存时间段内的最短路
    for(int i=1;i<=n;i++){
        f[i]=(long long)l[1][i]*i;//一直不改变路径的情况
        for(int j=1;j<i;j++){
            f[i]=min(f[i],f[j]+(i-j)*(long long)l[j+1][i]+k);
        }//对于之前的每一天，把这段时间改变路径，求min更新(这两个ll转换我调了半天）
    }
    printf("%d",f[n]);
    return 0;
}