网站整站下载,友情链接交换,学院网站建设 需求分析,成都市做网站公司1003: [ZJOI2006]物流运输 Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 8273 Solved: 3481[Submit][Status][Discuss]Description 物流公司要把一批货物从码头A运到码头B。由于货物量比较大#xff0c;需要n天才能运完。货物运输过程中一般要转停好几个码头。物流公司通… 1003: [ZJOI2006]物流运输 Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 8273 Solved: 3481[Submit][Status][Discuss] Description 物流公司要把一批货物从码头A运到码头B。由于货物量比较大需要n天才能运完。货物运输过程中一般要转停好几个码头。物流公司通常会设计一条固定的运输路线以便对整个运输过程实施严格的管理和跟踪。由于各种因素的存在有的时候某个码头会无法装卸货物。这时候就必须修改运输路线让货物能够按时到达目的地。但是修改路线是一件十分麻烦的事情会带来额外的成本。因此物流公司希望能够订一个n天的运输计划使得总成本尽可能地小。 Input 第一行是四个整数n1n100、m1m20、K和e。n表示货物运输所需天数m表示码头总数K表示每次修改运输路线所需成本。接下来e行每行是一条航线描述包括了三个整数依次表示航线连接的两个码头编号以及航线长度0。其中码头A编号为1码头B编号为m。单位长度的运输费用为1。航线是双向的。再接下来一行是一个整数d后面的d行每行是三个整数P 1 P m、a、b1 a b n。表示编号为P的码头从第a天到第b天无法装卸货物含头尾。同一个码头有可能在多个时间段内不可用。但任何时间都存在至少一条从码头A到码头B的运输路线。 Output 包括了一个整数表示最小的总成本。总成本n天运输路线长度之和K*改变运输路线的次数。 Sample Input 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 Sample Output 32 //前三天走1-4-5后两天走1-3-5这样总成本为(22)*3(32)*21032 题解预处理出第i-j天的最少花费cost[i,j]即第i-j天能连续走的最短路这样我们做n^2遍spfa然后直接dp即可。 初始化f[i]cost[1,i] 状态转移方程f[i]min(f[i],f[j]cost[j1,i]) 代码如下 1 #includecstdio2 #includeiostream3 #includecstring4 #define Max 100105 #define INF 21390621436 using namespace std;7 int n,m,K,E,d,dis[25],cost[105][105],f[105],q[25];8 int head[Max],cnt;9 bool vis[25],no[25][105],flag[25];
10 struct edge{int to,next,v;}e[Max];
11 void ins(int u,int v,int w){
12 e[cnt].tov;e[cnt].nexthead[u];head[u]cnt;e[cnt].vw;
13 e[cnt].tou;e[cnt].nexthead[v];head[v]cnt;e[cnt].vw;
14 }
15 int spfa(){
16 memset(dis,127,sizeof(dis)); dis[1]0;
17 memset(vis,0,sizeof(vis)); vis[1]true;
18 int hd0,tl1; q[hd]1;
19 while(hdtl){
20 int nowq[hd]; vis[now]false;
21 for(int ihead[now];i;ie[i].next)
22 if(dis[e[i].to]dis[now]e[i].v!flag[e[i].to]){
23 dis[e[i].to]dis[now]e[i].v;
24 if(!vis[e[i].to]){
25 vis[e[i].to]true; q[tl]e[i].to;
26 }
27 }
28 }
29 return dis[m];
30 }
31 void init(){
32 scanf(%d%d%d%d,n,m,K,E);
33 for(int i1;iE;i){
34 int u,v,w;
35 scanf(%d%d%d,u,v,w);
36 ins(u,v,w);
37 }
38 scanf(%d,d);
39 for(int i1;id;i){
40 int u,v,w;
41 scanf(%d%d%d,u,v,w);
42 for(int jv;jw;j) no[u][j]true;
43 }
44 }
45 void solve(){
46 for(int i1;in;i)
47 for(int ji;jn;j){
48 memset(flag,0,sizeof(flag));
49 for(int k1;km;k)
50 for(int li;lj;l) flag[k]|no[k][l];
51 cost[i][j]spfa();
52 }
53 for(int i1;in;i)
54 for(int ji;jn;j)
55 if(cost[i][j]INF) cost[i][j]*(j-i1);
56 memset(f,127,sizeof(f));
57 for(int i1;in;i) f[i]cost[1][i];
58 for(int i2;in;i)
59 for(int j1;ji;j)
60 f[i]min(f[i],f[j]cost[j1][i]K);
61 }
62 int main()
63 {
64 init();
65 solve();
66 printf(%d,f[n]);
67 return 0;
68 } 转载于:https://www.cnblogs.com/Beginner-/p/7449152.html
