描述 Description
物流公司要把一批货物从码头 A 运到码头 B。由于货物量比较大，需要 n 天才能运完。货物运输过程中一般要转停好几个码头。物流公司通常会设计一条固定的运输路线，以便对整个运输过程实施严格的管理和跟踪。由于各种因素的存在，有的时候某个码头会无法装卸货物。这时候就必须修改运输路线，让货物能够按时到达目的地。但是修改路线是一件十分麻烦的事情，会带来额外的成本。因此物流公司希望能够订一个 n 天的运输计划，使得总成本尽可能地小。
输入格式 InputFormat
第一行是四个整数 n（1<=n<=100）、m（1<=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 的运输路线。
输出格式 OutputFormat
包括了一个整数表示最小的总成本。总成本 = n 天运输路线长度之和 + K * 改变运输路线的次数。
样例输入 SampleInput
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
样例输出 SampleOutput
32
代码 Code
DP+SPFA。
用 f[i] 表示 1~i 天的最小总成本，方程为
\[ f[i]=Min \lbrace f[j]+(i-j)*cost[j,i]+k \rbrace ,0 \leq j < i \\\ f[0]=-k \]
其中 cost[j,i] 表示一条 j+1~i 天的都可使用的运输路线长度的最小值，可用 spfa 求出。
用类似前缀和的方法判断当前码头是否在该段时间均可通行，数组 c[i][j] 表示 i 号码头前 j 天中无法装卸货物的天数。当且仅当 c[i][y]-c[i][x]==0 时表示 i 号码头第 x+1 天到第 y 天均可用。
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;
const int inf=0x7fffffff/27.11;
int i,j,t,n,m,l,r,k,z,y,x;
inline void read(int &x)
{
x=0;char ch=getchar();
while (ch<'0' || ch>'9') ch=getchar();
while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
}
struct edge
{
int to,next,val;
}e[505];
bool used[25];
int E,p,head[25],f[105],c[25][105],dis[25];
int cnt=0;
deque <int> q;
inline void ins(int u,int v,int w)
{
e[++cnt].to=v;e[cnt].val=w;e[cnt].next=head[u];
head[u]=cnt;
}
int spfa(int x,int y)
{
int i,j,t,u,v,w;
int s=1;
memset(used,false,sizeof(used));
while (!q.empty()) q.pop_front();
for (i=1;i<=m;i++) dis[i]=inf;
used[s]=true;dis[s]=0;q.push_back(s);
while (!q.empty())
{
u=q.front();q.pop_front();used[u]=false;
for (i=head[u];i;i=e[i].next)
{
v=e[i].to;w=e[i].val;
if (c[v][y]-c[v][x]==0 && dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
if (!used[v])
{
used[v]=true;
if (!q.empty() && dis[q.front()]>dis[v]) q.push_front(v);
else q.push_back(v);
}
}
}
}
return dis[m];
}
int main()
{
memset(c,0,sizeof(c));
read(n);read(m);read(k);read(E);
for (i=1;i<=n;i++) f[i]=inf;
for (i=1;i<=E;i++)
{
read(x);read(y);read(z);
ins(x,y,z);
ins(y,x,z);
}
read(p);
for (i=1;i<=p;i++)
{
read(x);read(y);read(z);
for (j=y;j<=z;j++) c[x][j]=1;
}
for (i=1;i<=m;i++) for (j=1;j<=n;j++) c[i][j]+=c[i][j-1];
f[0]=-k;
for (i=1;i<=n;i++)
{
for (j=0;j<i;j++)
{
t=spfa(j,i);
if (t!=inf) f[i]=min(f[i],f[j]+(i-j)*t+k);
}
}
printf("%d\n",f[n]);
return 0;
}