BZOJ 1003 [ZJOI2006]物流运输

题目大意

给你一个图，图上每个点有些时候不可用，每天需要求出一个最短路，求最小的Σ(每天的长度)+Σ(更换路线个数)。

国赛结束啦~

作为国赛之后第一道题能够1A我也是很Excited哒~

这道题初步的打算是这样的：DP,使用数组下标对应每一条可能的路径。f[i]表示第i条路径所对应的最小花费。之后O(N*M)就结束了……

可是发现，并不能记录每条路径= =这就十分的GG

之后我们转化一下思路：既然点，边，天数不多，我们可以上网络流枚举所有可能的连续情况。f[i][j]表示从i天开始连续j天的最小花费。

首先考虑第一种可能：不更换路径。在这种情况下裸着上最短路（堆优化Dijkstra）就可以求出f[i][j]的初值。如果不改变路径就找不到最短路的话那么我们就直接设为极大值。

之后考虑更换路径。更换路径的话可以尝试使用DP——当然这次是区间DP。搞出一个k进行区间递推，将f[i][j]分成两段，表示需要进行切换。具体思路和实现和“矩阵”类似不做赘述。

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,k,e,d,inx,iny,inz,f[110][110],dis[22],to[820],nex[820],head[22],val[820],tot;
bool use[22][110],vis[22];
priority_queue <pair<int,int> >q;
void addedge(int tx,int ty,int tz)
{
    to[++tot]=ty,nex[tot]=head[tx],head[tx]=tot,val[tot]=tz;
    to[++tot]=tx,nex[tot]=head[ty],head[ty]=tot,val[tot]=tz;
}
bool check(int tx,int tl,int tr)
{
    for(int i=tl;i<=tr;++i) if(use[tx][i]) return false;
    return true;
}
void dijkstra(int tx,int ty)
{
    memset(dis,0x3f,sizeof dis);
    memset(vis,false,sizeof vis);
    dis[1]=0;
    while(!q.empty()) q.pop();
    q.push(make_pair(0,1));
    while(!q.empty())
    {
        int tmp=q.top().second;
        q.pop();
        if(vis[tmp]) continue;
        vis[tmp]=true;
        for(int i=head[tmp];i;i=nex[i])
            if(check(to[i],tx,ty)&&dis[to[i]]>dis[tmp]+val[i])
            {
                dis[to[i]]=dis[tmp]+val[i];
                q.push(make_pair(-dis[to[i]],to[i]));
            }
    }
    if(dis[m]==0x3f3f3f3f) f[tx][ty]=dis[m];
    else f[tx][ty]=dis[m]*(ty-tx+1);
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&k,&e);
    for(int i=1;i<=e;++i) scanf("%d%d%d",&inx,&iny,&inz),addedge(inx,iny,inz);
    scanf("%d",&d);
    for(int i=1;i<=d;++i)
    {
        scanf("%d%d%d",&inx,&iny,&inz);
        for(int i=iny;i<=inz;++i) use[inx][i]=true;
    }
    for(int i=1;i<=n;++i)
        for(int j=i;j<=n;++j)
            dijkstra(i,j);
    for(int i=2;i<=n;++i)
        for(int j=1;j+i<=n;++j)
            for(int s=1;s<i;++s)
                f[j][j+i]=min(f[j][j+i],f[j][j+s]+f[j+s+1][j+i]+k);
    printf("%d",f[1][n]);
    return 0;
}