Luogu

BZOJ

分析

设$f[i]$表示前$i$天花费的最小值。

设第$[l,r]$天从$1$到$m$的距离为$dis[l][r]$,这个可以通过$n^2$遍$\mathrm{SPFA}$求出来。

然后容易写出状态转移方程:

$f[i]=\min\limits_{j=0}^{i-1}\big[f[j]+dis[j+1][i]*(i-j)+K\big]$

边界是$f[0]=-K$,因为第一次选择路径是不算作更改路径的。

答案是$f[n]$。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
typedef long long ll;
using namespace std;

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

const int MAXN=100+10;

struct Edge { int v,w,nxt; };
Edge e[MAXN*200];
int head[MAXN],cnt=0;

inline void addEdge(int u,int v,int w) {
    e[++cnt].v=v,e[cnt].w=w,e[cnt].nxt=head[u],head[u]=cnt;
}

int n,m,K,E;
int kill[MAXN][MAXN],dis[MAXN][MAXN];

int d[MAXN],inq[MAXN],ok[MAXN];
inline void SPFA(int l,int r) {
    for (re int i=1;i<=m;++i) {
        ok[i]=1;
        for (re int j=l;j<=r;++j)
            if (kill[i][j]) { ok[i]=0; break; }
    }
    queue<int> Q;
    memset(d,0x3f,sizeof(d)); memset(inq,0,sizeof(inq));
    d[1]=0,inq[1]=1,Q.push(1);
    while (!Q.empty()) {
        int u=Q.front(); Q.pop();
        inq[u]=0;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v,w=e[i].w; if (!ok[v]) continue;
            if (d[u]+w<d[v]) {
                d[v]=d[u]+w;
                if (!inq[v]) { inq[v]=1; Q.push(v); }
            }
        }
    }
    dis[l][r]=d[m];
}

ll f[MAXN]; //f[i]表示前i天花费的最小值

int main() {
    n=read(),m=read(),K=read(),E=read();
    for (re int i=1,u,v,w;i<=E;++i) {
        u=read(),v=read(),w=read();
        addEdge(u,v,w);
        addEdge(v,u,w);
    }
    int d=read();
    for (re int i=1,p,a,b;i<=d;++i) {
        p=read(),a=read(),b=read();
        for (re int j=a;j<=b;++j) kill[p][j]=1;
    }
    for (re int i=1;i<=n;++i)
        for (re int j=i;j<=n;++j)
            SPFA(i,j);
    f[0]=-K;
    for (re int i=1;i<=n;++i) {
        f[i]=2e14;
        for (re int j=0;j<i;++j)
            f[i]=min(f[i],f[j]+1ll*dis[j+1][i]*(i-j)+K);
    }
    printf("%lld\n",f[n]);
    return 0;
}
最后修改:2019 年 09 月 24 日 08 : 57 PM