首页 > 其他 > 详细

BZOJ_1003_[ZJOI2006]物流运输_最短路+dp

时间:2018-02-21 19:16:27      阅读:52      评论:0      收藏:0      [点我收藏+]

标签:tar   长度   scanf   bsp   oid   wap   ems   blank   tin   

BZOJ_1003_[ZJOI2006]物流运输_最短路+dp

题意:http://www.lydsy.com/JudgeOnline/problem.php?id=1003

分析:

这种一段一段的显然要用dp求。

f[i]表示到第i天为止的最小花销。转移有f[i]=min{f[j-1]+cost[j][i]*(i-j+1)+k};

其中cost[i][j]表示从i到j天的最短路长度,spfa预处理出来。

代码:

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4 using namespace std;
 5 int head[30],to[1000],nxt[1000],val[1000],cnt;
 6 int n,m,k,t,inb[110][30],f[110],cost[110][110],can[30];
 7 int Q[100],l,r,dis[30],inq[30];
 8 inline void add(int u,int v,int w){
 9     to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;val[cnt]=w;    
10 }
11 int spfa(int be,int en){
12     for(int i=1;i<=n;i++)can[i]=0;
13     for(int i=be;i<=en;i++)
14         for(int j=1;j<=n;j++)if(inb[i][j])
15             can[j]=1;
16     l=r=0;
17     memset(dis,0x3f,sizeof(dis));
18     dis[1]=0;Q[r++]=1;inq[1]=1;
19     while(l^r){
20         int x=Q[l++];if(l==n+10)l=0;inq[x]=0;    
21         for(int i=head[x];i;i=nxt[i]){
22             if(can[to[i]])continue;
23             if(dis[to[i]]>dis[x]+val[i]){
24                 dis[to[i]]=dis[x]+val[i];
25                 if(!inq[to[i]]){
26                     inq[to[i]]=1;Q[r++]=to[i];if(r==n+10)r=0;    
27                 }
28             }
29         }
30     }
31     return dis[n]>100000?-1:dis[n];
32 }
33 int main(){
34     scanf("%d%d%d%d",&t,&n,&k,&m);
35     int x,y,z;
36     for(int i=1;i<=m;i++){
37         scanf("%d%d%d",&x,&y,&z);
38         add(x,y,z);add(y,x,z);
39     }
40     int h;
41     scanf("%d",&h);
42     for(int i=1;i<=h;i++){
43         scanf("%d%d%d",&x,&y,&z);
44         if(y>z)swap(y,z);
45         for(int j=y;j<=z;j++)inb[j][x]=1;
46     }
47     for(int i=1;i<=t;i++){
48         for(int j=i;j<=t;j++){
49             cost[i][j]=spfa(i,j);
50             //printf("%d\n",cost[i][j]);
51         }
52     }
53     f[0]=0;
54     for(int i=1;i<=t;i++){
55         f[i]=1<<30;
56         for(int j=1;j<=i;j++){
57             if(cost[j][i]==-1)continue;
58             f[i]=min(f[j-1]+cost[j][i]*(i-j+1)+k,f[i]);
59         }
60         //printf("%d\n",f[i]);
61     }
62     printf("%d",f[t]-k);
63 }

 

BZOJ_1003_[ZJOI2006]物流运输_最短路+dp

标签:tar   长度   scanf   bsp   oid   wap   ems   blank   tin   

原文:https://www.cnblogs.com/suika/p/8457057.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号