专栏首页数据结构与算法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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Kosaraju算法详解

    Kosaraju算法可以求出有向图中的强连通分量个数,并且对分属于不同强连通分量的点进行标记。它的算法描述较为简单: (1) 第一次对图G进行DFS遍历,并在...

    attack
  • P1197 [JSOI2008]星球大战

    题目描述 很久以前,在一个遥远的星系,一个黑暗的帝国靠着它的超级武器统治者整个星系。某一天,凭着一个偶然的机遇,一支反抗军摧毁了帝国的超级武器,并攻下了星系中几...

    attack
  • 洛谷P3763 [TJOI2017]DNA(后缀数组 RMQ)

    具体来说,每次比较当前后缀和\(S_0\)的lcp,如果长度\(< N\)的话就从不合法的位置继续匹配

    attack
  • 对比 Dijkstra Bellman—Ford Spfa 最短路之间区别

    本质上Dijkstra是一种贪心,满足局部最优,每次找的是离起点最近的(保证了这个点的距离就是最短路),如果有负边权,当前找到的就不一定是最近的了。

    ACM算法日常
  • 2017.5.13阶段模拟考试

    预计分数:100+50(其实感觉自己写的对)+100 实际分数:100+0+100 P1149 火柴棒等式 题目描述 给你n根火柴棍,你可以拼出多少个形如“A+...

    attack
  • POJ 刷题系列:3349. Snowflake Snow Snowflakes

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/...

    用户1147447
  • 看动画轻松理解时间复杂度(一)

    算法(Algorithm)是指用来操作数据、解决程序问题的一组方法。对于同一个问题,使用不同的算法,也许最终得到的结果是一样的,比如排序就有前面的十大经典排序和...

    五分钟学算法
  • 洛谷P3763 [TJOI2017]DNA(后缀数组 RMQ)

    具体来说,每次比较当前后缀和\(S_0\)的lcp,如果长度\(< N\)的话就从不合法的位置继续匹配

    attack
  • 【CodeForces 730H】Car Repair Shop

    模拟,先看从s[i]时刻开始修理,和之前i-1个是否冲突。如果冲突,就枚举每个s[j]+d[j]时刻开始,看是否冲突,再从中选择最小的时刻。

    饶文津
  • poj 2681 字符串

    瑾诺学长

扫码关注云+社区

领取腾讯云代金券