bzoj 1003

bzoj

题目

Solution

首先要预处理出对于任意的 i<=j<=day 第i到j天的最短路//这里存放在cost中

然后用动态规划来解决所有天数里可行的的最小值

状态转移方程

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXM 1100
using namespace std;
int day,n,K,m,tot;
struct E{
    int next,to,val;
}edge[MAXM];
int head[MAXM],edge_num;
int block[MAXM][MAXM];
int mark[MAXM];
int cost[MAXM][MAXM];
int dis[MAXM],inque[MAXM];
queue<int> que;
int dp[MAXM];
int inf;
void addedge(int x,int y,int z){
    edge[++edge_num].next=head[x];
    edge[edge_num].to=y;
    edge[edge_num].val=z;
    head[x]=edge_num;
}
int SPFA(){
    memset(dis,0x7f,sizeof(dis));
    inf=dis[0];
    inque[1]=1;
    dis[1]=0;
    que.push(1);
    while(!que.empty()){
        int fro=que.front();que.pop();inque[fro]=0;
        int i;
        for(i=head[fro];i;i=edge[i].next){
        if(dis[edge[i].to]>dis[fro]+edge[i].val && !mark[edge[i].to]){
                dis[edge[i].to]=dis[fro]+edge[i].val;
                if(!inque[edge[i].to]){
                    que.push(edge[i].to);
                    inque[edge[i].to]=1;
                }
            }
        }
    }
    return dis[n];
}
int DP(){
    int i,j;
    for(i=1;i<=day;i++)
        dp[i]=cost[1][i];
    for(i=2;i<=day;i++){
        for(j=1;j<i;j++){
            dp[i]=min(dp[j]+cost[j+1][i]+K,dp[i]);
        }
    }
    return dp[day];
}
void solve(){
    int i,j,k,l;
    for(i=1;i<=day;i++){
        for(j=i;j<=day;j++){
            memset(mark,0,sizeof(mark));
            for(k=1;k<=n;k++){
                for(l=i;l<=j;l++){
                    mark[k]|=block[k][l];
                }
            }
            cost[i][j]=SPFA();
        }
    }
    for(i=1;i<=day;i++){
        for(j=i;j<=day;j++){
            if(cost[i][j]!=inf)
                cost[i][j]*=(j-i+1);
        }
    }
    printf("%d\n",DP());
}
int main(){
    freopen("bz.in","r",stdin);
    scanf("%d%d%d%d",&day,&n,&K,&m);
    int i;
    for(i=1;i<=m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        addedge(a,b,c);
        addedge(b,a,c);
    }
    scanf("%d",&tot);
    for(i=1;i<=tot;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        for(int j=b;j<=c;j++)
            block[a][j]=1;
    }
    solve();
    return 0;
}