[文章目录]
Description
物流公司要把一批货物从码头A运到码头B。由于货物量比较大，需要n天才能运完。货物运输过程中一般要转停m个码头中的几个。物流公司通常会设计一条固定的运输路线，以便对整个运输过程实施严格的管理和跟踪。由于各种因素的存在，有的时候某个码头会无法装卸货物。这时候就必须修改运输路线，让货物能够按时到达目的地。但是修改路线是一件十分麻烦的事情，会带来额外的成本。因此物流公司希望能够订一个n天的运输计划，使得总成本尽可能地小。n<=100 m<=20
预处理每个时间段从始至终码头都可用的状态下的最短路，之后区间DP即可。时间复杂度O(n^2*spfa)。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int n,m,K,e,d,mp[25][25];
int q[500],dis[25],ex[110];
ll f[110][110],dp[110];
bool vis[25];
int spfa()
{
memset(dis,0x3f,sizeof dis);
dis[1]=0; q[1]=1; int i,x,l=1,r=1;
while(l<=r)
{
x=q[l++]; vis[x]=0;
for(i=1;i<=m;++i) if(dis[x]+mp[x][i]<dis[i])
{
dis[i]=dis[x]+mp[x][i];
if(!vis[i]) q[++r]=i,vis[i]=1;
}
}
return dis[m];
}
int main()
{
scanf("%d%d%d%d",&n,&m,&K,&e);
int i,j,k,x,y,z;
memset(mp,0x3f,sizeof mp);
for(i=1;i<=e;++i)
{
scanf("%d%d%d",&x,&y,&z);
if(z<mp[x][y]) mp[x][y]=mp[y][x]=z;
}
scanf("%d",&d);
for(i=1;i<=d;++i)
{
scanf("%d%d%d",&x,&y,&z);
while(y<=z) ex[y]|=1<<(x-1),++y;
}
for(i=1;i<=n;++i)
{
x=0;
for(j=i;j<=n;++j)
{
x|=ex[j];
for(k=0;k<m;++k) vis[k+1]=(x>>k)&1;
f[i][j]=spfa();
}
}
for(i=1;i<=n;++i)
{
dp[i]=f[1][i]*i;
for(j=2;j<=i;++j)
dp[i]=min(dp[i],dp[j-1]+f[j][i]*(i-j+1)+K);
}
printf("%lld",dp[n]);
return 0;
}