洛谷P1772 [ZJOI2006]物流运输

zrzring 2020-04-11 PM 300℃ 0条

题意:给你m个码头,n天,每天都要从1走到m,给定一些码头在某些时候不能通行,每一天1到m的路径和前一天不同就需要额外K的价值,求这n天每天从1到m的距离和与更改道路的价值之和的最小值

每天走最短路的贪心可能会导致额外价值很大

可以$dp$,记录第$i$到$j$天都走相同的道路的价值为$cost[i][j]$,这个直接把这几天里所有不能走的点都封上,总计做$n^2$次最短路就行

问题转化为一个简单的$dp$,记$dp[i]$表示前$i$天的最小价值,递推式

$$ dp[i]=min(cost[1][i]\times i,{dp[j]+cost[j+1][i]\times (i-j)+K}),1\leq j\leq i-1 $$

//我自定义的变量名,和题目定义的不一样
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#define mp(x,y) make_pair(x,y)
using namespace std;
void file(){
    freopen("read.in","r",stdin);
    freopen("write.out","w",stdout);
}
const int N=1010;
inline int read(){
    int sym=0,res=0;char ch=getchar();
    while (!isdigit(ch))sym|=(ch=='-'),ch=getchar();
    while (isdigit(ch))res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
    return sym?-res:res;
}
struct EDGE{
    int ver,nxt,dis;
}edge[N];
int n,m,T,w,head[N],cnt,no[N][N],cost[N][N],vis[N],dis[N],dp[N];
void add(int u,int v,int t){
    edge[++cnt]=(EDGE){v,head[u],t};
    head[u]=cnt;
}
priority_queue<pair<int,int> >q;
void dij(){
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;q.push(mp(0,1));
    while (!q.empty()){
        int u=q.top().second;q.pop();if (vis[u])continue;vis[u]=1;
        for (int i=head[u];i;i=edge[i].nxt){
            int v=edge[i].ver;if (vis[v])continue;
            if (dis[u]+edge[i].dis<dis[v]){
                dis[v]=dis[u]+edge[i].dis;q.push(mp(-dis[v],v));
            }
        }
    }
}
int main(){
    T=read();n=read();w=read();m=read();
    for (int i=1;i<=m;i++){
        int u=read(),v=read(),t=read();add(u,v,t);add(v,u,t);
    }
    int D=read();
    for (int i=1;i<=D;i++){
        int x=read(),l=read(),r=read();
        for (int j=l;j<=r;j++)no[x][j]=1;
    }
    for (int l=1;l<=T;l++){
        for (int r=l;r<=T;r++){
            memset(vis,0,sizeof(vis));
            for (int t=l;t<=r;t++){
                for (int i=1;i<=n;i++){
                    if(no[i][t])vis[i]=1;
                }
            }
            dij();cost[l][r]=dis[n];printf("%d\n",dis[n]);
        }
    }
    memset(dp,0x7f,sizeof(dp));
    for (int i=1;i<=T;i++){
        dp[i]=1ll*cost[1][i]*i;
        for (int j=i-1;j>=0;j--){
            dp[i]=min(dp[i],dp[j]+cost[j+1][i]*(i-j)+w);
        }
    }
    printf("%lld",dp[T]);
    return 0;
}
Title - Artist
0:00