luogu 1772 物流运输 ZJOI2006 spfa+dp

主要路径上存在时间限制(消失)

因为数据较小(点数较小)，利用限制条件在规定时间内分别spfa,(也可用floyd)

再通过dp取最优值

#include<bits/stdc++.h>

#define ll long long

#define rep(i,x,y) for(register int i=x;i<=y;i++)

using namespace std;

inline int read(){

    int x=,f=;char ch=getchar();

    while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}

    while(isdigit(ch)){x=(x<<)+(x<<)+(ch^);ch=getchar();}

    return x*f;}

const int N=;

const int M=;

const int T=;

const int inf=0x3f3f3f3f;

int day,n,rec,m,d,t,dis[N];

int close[N][T],now[N],vis[N];

ll cost[T][T],f[T];

int head[N],tot;

struct node{int v,w,next;}e[M];

void insert(int u,int v,int w){

    e[++tot]=(node){v,w,head[u]};head[u]=tot;

    e[++tot]=(node){u,w,head[v]};head[v]=tot;}

int spfa(int x,int y){

    memset(dis,inf,sizeof dis);

    memset(vis,,sizeof vis);

    memset(now,,sizeof now);

    rep(i,,n)rep(j,x,y)

    if(close[i][j]) now[i]=;

    queue<int> q;

    q.push();dis[]=;vis[]=;

    while(!q.empty()){

        int u=q.front();q.pop();vis[u]=;

        for(int i=head[u];i;i=e[i].next){

            int v=e[i].v,w=e[i].w;

            if(now[v]) continue;

            if(dis[u]+w<dis[v]){

                dis[v]=dis[u]+w;

                if(!vis[v]) vis[v]=,q.push(v);

            }

        }

    }return dis[n];

}

int main(){

    day=read(),n=read(),rec=read(),m=read();

    rep(i,,m){

        int u=read(),v=read(),w=read();insert(u,v,w);}

    t=read();

    rep(i,,t){

        int p=read(),u=read(),v=read();

        rep(j,u,v) close[p][j]=;}

    rep(i,,day)rep(j,,day)

        cost[i][j]=spfa(i,j);

    rep(i,,day){

        f[i]=(ll)cost[][i]*i;

        rep(j,,i)

        f[i]=min(f[i],f[j]+(ll)cost[j+][i]*(i-j)+rec);}

    printf("%lld\n",f[day]); return ;

}