物流公司要把一批货物从码头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 }