@zzzc18 2017-05-11T03:44:32.000000Z 字数 1598 阅读 1120

# bzoj 1003

bzoj

## Solution

#include<queue>#include<cstdio>#include<cstring>#include<algorithm>#define MAXM 1100using 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;}

• 私有
• 公开
• 删除