[zjoi2006]物流运输 （洛谷1772）

Posted by yjjr's blog on February 6, 2018

5 510 8

1 21

1 33

1 42

2 32

2 44

3 41

3 52

4 52

4

2 23

3 11

3 33

4 45

32

Code

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define LL long long
#define mem(x,num) memset(x,num,sizeof x)
using namespace std;
const int inf=0x3f3f3f,maxn=106,maxm=26;
struct edge
{
int to,next,w;
}e[maxn*10];
int cnt,last[maxm],n,m,k,d,q;
bool flag[maxn][maxm];
LL Map[maxn][maxn],f[maxn];
inline void ins(int u,int v,int w){
e[++cnt]=(edge){v,last[u],w};
last[u]=cnt;
e[++cnt]=(edge){u,last[v],w};
last[v]=cnt;
}

int spfa(int a,int b){
bool block[maxm];
int dis[maxm],q[maxn*10],inq[maxm];
mem(block,0);mem(dis,inf);mem(inq,0);
rep(i,a,b)
rep(j,1,m)
if(flag[i][j])block[j]=1;
q[0]=1;inq[1]=1;dis[1]=0;
while(p){
if(!inq[e[p].to]){q[tail++]=e[p].to;inq[e[p].to]=1;}
}
p=e[p].next;
}
}
return dis[m];
}

void dp()
{
rep(i,1,n){
f[i]=(LL)Map[1][i]*i;
rep(j,0,i-1)
f[i]=min(f[i],f[j]+k+Map[j+1][i]*(i-j));
}
}
int main()
{
scanf("%d%d%d%d",&n,&m,&k,&q);
rep(i,1,q){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
ins(u,v,w);
}
scanf("%d",&d);
rep(i,1,d){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
rep(j,v,w)flag[j][u]=1;
}
rep(i,1,n)
rep(j,1,n)Map[i][j]=spfa(i,j);
dp();
printf("%d\n",f[n]);
return 0;
}