首页 > 代码库 > P1772 [ZJOI2006]物流运输
P1772 [ZJOI2006]物流运输
题目描述
物流公司要把一批货物从码头A运到码头B。由于货物量比较大，需要n天才能运完。货物运输过程中一般要转停好几个码头。物流公司通常会设计一条固定的运输路线，以便对整个运输过程实施严格的管理和跟踪。由于各种因素的存在，有的时候某个码头会无法装卸货物。这时候就必须修改运输路线，让货物能够按时到达目的地。但是修改路线是—件十分麻烦的事情，会带来额外的成本。因此物流公司希望能够订一个n天的运输计划，使得总成本尽可能地小。
输入输出格式
输入格式：
第一行是四个整数n(l≤n≤100)、m(l≤m≤20)、K和e。n表示货物运输所需天数，m表示码头总数，K表示每次修改运输路线所需成本。接下来e行每行是一条航线描述，包括了三个整数，依次表示航线连接的两个码头编号以及航线长度(>0)。其中码头A编号为1，码头B编号为m。单位长度的运输费用为1。航线是双向的。再接下来一行是一个整数d，后面的d行每行是三个整数P(1<P<m)，a，b(1≤a≤b≤n)。表示编号为P的码头从第a天到第b天无法装卸货物（含头尾）。同一个码头有可能在多个时间段内不可用。但任何时间都存在至少一条从码头A到码头B的运输路线。
输出格式：
包括了一个整数表示最小的总成本。总成本=n天运输路线长度之和+K*改变运输路线的次数。
输入输出样例
输入样例#1：
5 5 10 8 1 2 1 1 3 3 1 4 2 2 3 2 2 4 4 3 4 1 3 5 2 4 5 2 4 2 2 3 3 1 1 3 3 3 4 4 5
输出样例#1：
32
说明
【样例输入说明】
上图依次表示第1至第5天的情况，阴影表示不可用的码头。
【样例输出说明】
前三天走1-4-5，后两天走1-3-5，这样总成本为(2+2)*3+(3+2)*2+10=32。
_NOI导刊2010提高（01）
通过SPFA预处理COST数组，
用F数组记录到第i天的最小花费
cost[i][j]表示从第i天到第j天的最小花费
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<queue> 6 #include<algorithm> 7 #define lli long long int 8 using namespace std; 9 const int MAXN=2333; 10 const int INF=0x7ffff; 11 void read(int &n) 12 { 13 char c=‘+‘;int x=0;bool flag=0; 14 while(c<‘0‘||c>‘9‘) 15 {c=getchar();if(c==‘-‘)flag=1;} 16 while(c>=‘0‘&&c<=‘9‘) 17 {x=x*10+(c-48);c=getchar();} 18 flag==1?n=-x:n=x; 19 } 20 int day,n,spend,m,stopnum; 21 struct node 22 { 23 int u,v,w,nxt; 24 }edge[MAXN]; 25 int head[MAXN]; 26 int num=1; 27 int vis[MAXN]; 28 void add_edge(int x,int y,int z) 29 { 30 edge[num].u=x; 31 edge[num].v=y; 32 edge[num].w=z; 33 edge[num].nxt=head[x]; 34 head[x]=num++; 35 } 36 struct s 37 { 38 int bg,ed; 39 }stop[MAXN]; 40 int f[MAXN],cost[MAXN][MAXN]; 41 int dis[MAXN]; 42 int pd[MAXN][MAXN]; 43 44 void init() 45 { 46 read(day);read(n);read(spend);read(m); 47 for(int i=1;i<=n;i++) 48 head[i]=-1; 49 for(int i=1;i<=m;i++) 50 { 51 int x,y,z; 52 read(x);read(y);read(z); 53 add_edge(x,y,z); 54 add_edge(y,x,z); 55 } 56 read(stopnum); 57 for(int i=1;i<=stopnum;i++) 58 { 59 int x,y,z; 60 read(x);read(y);read(z); 61 for (int j=y; j<=z; ++j) 62 pd[x][j] = true; 63 } 64 } 65 bool juge(int v,int a,int b) 66 { 67 for (int i=a; i<=b; ++i) 68 if (pd[v][i]) 69 return false; 70 return true; 71 } 72 int SPFA(int x,int y) 73 { 74 memset(vis,0,sizeof(vis)); 75 for(int i=2;i<=n;i++) 76 dis[i]=INF; 77 queue<int>q; 78 q.push(1); 79 vis[1]=1; 80 int will=1; 81 if (!juge(1,x,y)) 82 //if((stop[will].bg>=x&&stop[will].ed<=y)||(stop[will].bg<=y&&stop[will].ed>=y)||(stop[will].bg<=x&&stop[will].ed>=x)) 83 return INF; 84 while(q.size()!=0) 85 { 86 int p=q.front(); 87 q.pop(); 88 vis[p]=0; 89 for(int i=head[p];i!=-1;i=edge[i].nxt) 90 { 91 int will=edge[i].v; 92 // if((stop[will].bg>=x&&stop[will].ed<=y)||(stop[will].bg<=y&&stop[will].ed>=y)||(stop[will].bg<=x&&stop[will].ed>=x)||(stop[will].bg<=x&&stop[will].ed>=y)) 93 //continue; 94 if (!juge(will,x,y)) continue; 95 if(dis[will]>dis[edge[i].u]+edge[i].w) 96 { 97 dis[will]=dis[edge[i].u]+edge[i].w; 98 if(!vis[will]) 99 {100 q.push(will);101 vis[will]=1;102 }103 }104 105 }106 }107 return dis[n]*(y-x+1);108 }109 void pre()110 {111 for(int i=1;i<=day;i++)112 for(int j=1;j<=day;j++)113 cost[i][j]=INF,f[i]=INF;114 for(int i=1;i<=day;i++)115 for(int j=i;j<=day;j++)116 cost[i][j]=SPFA(i,j);117 for(int i=1;i<=day;i++)118 f[i]=cost[1][i];119 }120 void DP()121 {122 f[0]=0;123 for(int i=2;i<=day;i++)124 for(int j=i-1;j>=1;j--)125 if(cost[j+1][i]!=INF)126 f[i]=min(f[i],f[j]+cost[j+1][i]+spend);127 else 128 break;129 printf("%d",f[day]);130 }131 int main()132 {133 //freopen("bzoj_1003.in","r",stdin);134 //freopen("bzoj_1003.out","w",stdout);135 init();136 pre();137 DP();138 return 0;139 }
P1772 [ZJOI2006]物流运输
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。