【BZOJ1003】【ZJOI2006】物流运输

以前~~版刷BZOJ~~的时候见过这道题来着然后没看懂

现在还是绕不开了

意思是给你一个图，有一些点在某些时间段不能走，每个时间点要有一条从1到m的路径，产生路径长度的代价，并且每个时间点将路径变更的代价为K。求最小代价和。

看到数据范围很小，首先枚举时间端点l、r，预处理[l,r]不变更路径的最小代价。然后就可以随意dp了。

// <1003.cpp> - 05/14/16 17:41:26
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
using namespace std;
typedef long long lol;
int gi(){
    int res=0,fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    return fh*res;
}
const int MAXN=110;
const int INF=1e7;
int bt,b[MAXN],next[1001],to[1001],val[1001];
inline void add(int v,int x,int y){
    next[++bt]=b[x];b[x]=bt;to[bt]=y;val[bt]=v;
    next[++bt]=b[y];b[y]=bt;to[bt]=x;val[bt]=v;
}
bool ban[MAXN][MAXN],ded[MAXN];
int sum[MAXN][MAXN];
int n,m,dis[MAXN];
queue <int> q;
bool in[MAXN];
inline int spfa(){
    for(int i=2;i<=m;i++)dis[i]=INF;
    q.push(1);in[1]=1;
    while(!q.empty()){
        int now=q.front();q.pop();in[now]=0;
        for(int i=b[now];i;i=next[i])
            if(!ded[to[i]]&&dis[now]+val[i]<dis[to[i]]){
                dis[to[i]]=dis[now]+val[i];
                if(!in[to[i]]){q.push(to[i]);in[to[i]]=1;}
            }
    }
    return dis[m];
}
int dp[MAXN];
int main(){
    n=gi(),m=gi();
    int K=gi(),e=gi();
    for(int i=1;i<=e;i++)add(gi(),gi(),gi());
    int d=gi();
    while(d--){
        int g=gi(),l=gi(),r=gi();
        for(int i=l;i<=r;i++)ban[g][i]=1;
    }
    for(int l=1;l<=n;l++)
        for(int r=l;r<=n;r++){
            for(int i=2;i<m;i++){
                ded[i]=0;
                for(int j=l;j<=r;j++)
                    if(ban[i][j]){ded[i]=1;break;}
            }
            sum[l][r]=spfa();
        }
    for(int i=1;i<=n;i++){
        dp[i]=i*sum[1][i];
        for(int j=1;j<i;j++)dp[i]=min(dp[i],dp[j]+K+(i-j)*sum[j+1][i]);
    }
    printf("%d",dp[n]);
    return 0;
}

// <1003.cpp> - 05/14/16 17:41:26

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <queue>

using namespace std;

typedef long long lol;

int gi(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

const int MAXN=110;

const int INF=1e7;

int bt,b[MAXN],next[1001],to[1001],val[1001];

inline void add(int v,int x,int y){

next[++bt]=b[x];b[x]=bt;to[bt]=y;val[bt]=v;

next[++bt]=b[y];b[y]=bt;to[bt]=x;val[bt]=v;

}

bool ban[MAXN][MAXN],ded[MAXN];

int sum[MAXN][MAXN];

int n,m,dis[MAXN];

queue <int> q;

bool in[MAXN];

inline int spfa(){

for(int i=2;i<=m;i++)dis[i]=INF;

q.push(1);in[1]=1;

while(!q.empty()){

int now=q.front();q.pop();in[now]=0;

for(int i=b[now];i;i=next[i])

if(!ded[to[i]]&&dis[now]+val[i]<dis[to[i]]){

dis[to[i]]=dis[now]+val[i];

if(!in[to[i]]){q.push(to[i]);in[to[i]]=1;}

}

return dis[m];

}

int dp[MAXN];

int main(){

n=gi(),m=gi();

int K=gi(),e=gi();

for(int i=1;i<=e;i++)add(gi(),gi(),gi());

int d=gi();

while(d--){

int g=gi(),l=gi(),r=gi();

for(int i=l;i<=r;i++)ban[g][i]=1;

}

for(int l=1;l<=n;l++)

for(int r=l;r<=n;r++){

for(int i=2;i<m;i++){

ded[i]=0;

for(int j=l;j<=r;j++)

if(ban[i][j]){ded[i]=1;break;}

}

sum[l][r]=spfa();

}

for(int i=1;i<=n;i++){

dp[i]=i*sum[1][i];

for(int j=1;j<i;j++)dp[i]=min(dp[i],dp[j]+K+(i-j)*sum[j+1][i]);

}

printf("%d",dp[n]);

return 0;

}