洛谷1772 [ZJOI2006]物流运输

题意

有一个 $m(m\le 20)$ 个点 $e$ 条边的无向图，有 $n(n\le 100)$ 个时刻需要从 $1\rightarrow m$ （保证可以到达）。每个点都有些时刻无法通行，如果更换道路还需要额外交 $k$ 元。求最小花费。

题解

用 $f[i]$ 表示前 $i$ 个时刻的最小花费，$x$ 表示最短路径。枚举与 $i$ 路径相同的区间起点 $j$ ，可以得到方程：

$$f[i]=\min f[j-1]+(i-j+1)\times x + k$$

倒序枚举 $j$ ，就可以得到 $[j,i]$ 时刻所有无法通行的点，绕开这些点跑最短路就可以得到 $x$ 。

初值为 $f[0]=-k$ ，因为第一次更换不需要花费。

#include<bits/stdc++.h>
#define mp make_pair
#define pii pair<int,int>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

struct Edge {
    int next,to,w;
} edge[805];
const int inf=0x3f3f3f3f;
bool no[25][105],vis[25],cur[25];
int n,m,k,e,d,a,b,c,cnt,head[25],dis[25],f[105];

inline void add(int u,int v,int w)
{
    edge[++cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

inline int dijkstra()
{
    memset(vis,0,sizeof(vis));
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;
    priority_queue <pii,vector<pii>,greater<pii> > q;
    q.push(mp(0,1));
    while (!q.empty())
    {
        int x=q.top().second; q.pop();
        if (vis[x] || cur[x]) continue;
        vis[x]=1;
        for (int i=head[x];i;i=edge[i].next)
        {
            int y=edge[i].to,w=edge[i].w;
            if (dis[x]+w<dis[y])
            {
                dis[y]=dis[x]+w;
                q.push(mp(dis[y],y));
            }
        }
    }
    return dis[m];
}

signed main()
{
    n=read(); m=read(); k=read(); e=read();
    for (int i=1;i<=e;i++)
    {
        a=read(); b=read(); c=read();
        add(a,b,c);
        add(b,a,c);
    }
    d=read();
    while (d--)
    {
        a=read(); b=read(); c=read();
        for (int i=b;i<=c;i++) no[a][i]=1;
    }
    memset(f,0x3f,sizeof(f));
    f[0]=-k;
    for (int i=1;i<=n;i++)
    {
        memset(cur,0,sizeof(cur));
        for (int j=i;j;j--)
        {
            for (int k=1;k<=m;k++) if (no[k][j]) cur[k]=1; //合并当前时刻无法通行的点
            int res=dijkstra();
            if (res==inf) break; //无法连通
            f[i]=min(f[i],f[j-1]+(i-j+1)*res+k);
        }
    }
    return !printf("%d",f[n]);
}