Description
物 流公司要把一批货物从码头A运到码头B。由于货物量比较大，需要n天才能运完。货物运输过程中一般要转停好几个码头。物流公司通常会设计一条固定的运输路 线，以便对整个运输过程实施严格的管理和跟踪。由于各种因素的存在，有的时候某个码头会无法装卸货物。这时候就必须修改运输路线，让货物能够按时到达目的 地。但是修改路线是一件十分麻烦的事情，会带来额外的成本。因此物流公司希望能够订一个n天的运输计划，使得总成本尽可能地小。
动规，f（i）=f(j)+c(i,j);
c表示从i天到j天的最小钱数。
跑了N方次SPFA真心不敢想啊ORZ
注意n和m不要弄混。。。（不要问我为啥这样说。。。）
/**************************************************************
Problem: 1003
User: 1115825064
Language: C++
Result: Accepted
Time:40 ms
Memory:1588 kb
****************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct D{
int to,next,w;
}e[10001];
int head1[23],tot=0;
#define LINK(x) for(int i=head1[x];i;i=e[i].next)
void jia(int u,int v,int w)
{
e[++tot].w=w,e[tot].to=v,e[tot].next=head1[u];head1[u]=tot;
}
int n,m,k,e1;
bool g[30][101];
int cost[101][101],que[40005],head,tail;
int f[102];
int main()
{
// freopen("1.txt","r",stdin);
scanf("%d%d%d%d",&n,&m,&k,&e1);
for(int i=1;i<=e1;++i)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
jia(a,b,c);
jia(b,a,c);
}
int d1;
scanf("%d",&d1);
while(d1--)
{
int a,b,c;
scanf("%d%d%d",&c,&a,&b);
if(a>b) swap(a,b);
for(int j=a;j<=b;++j)
{
g[c][j]=1;
}
}
bool d[30],g1[30];
for(int i1=1;i1<=n;++i1)
for(int j=i1;j<=n;++j)
{
memset(d,0,sizeof(d));
memset(g1,0,sizeof(g1));
for(int a1=1;a1<=m;++a1)
for(int a2=i1;a2<=j;++a2)
{
if(g[a1][a2]) {
g1[a1]=1;
break;
}
}
for(int i=1;i<=m;++i)
f[i]=100000000;
f[1]=0;
head=0;tail=1;
que[1]=1;
while(head!=tail)
{
head%=40000;
head++;
int x=que[head];
d[x]=0;
LINK(x)
if(f[e[i].to]>f[x]+e[i].w&&!g1[e[i].to])
{
f[e[i].to]=f[x]+e[i].w;
if(d[e[i].to]==0)
{
tail%=40000;
que[++tail]=e[i].to;
d[e[i].to]=1;
}
}
}
cost[i1][j]=f[m];
}
for(int i=1;i<=n;++i)
f[i]=100000000;
f[0]=0;
for(int i=1;i<=n;++i)
for(int j=0;j<i;++j)
f[i]=min(f[i],f[j]+k+cost[j+1][i]*(cost[j+1][i]>=100000000?1:i-j));
printf("%d",f[n]-k);
return 0;
}
评论 (0)
