题解 P1772 【[ZJOI2006]物流运输】

spfa+dp。。。 难想的主要是dp部分，这里只用一维。用dp[i]表示第i天 所用的最小花费。如果用v[i][j]表示i~j天不改变路线的最小花费，则转移方程就是：dp[i]=min(dp[i],d[j]+v[j+1][i]+k) 那么问题就是怎么求v。很简单，枚举一下i和j，直接暴力用spfa求。 ```cpp #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n,m,k,e,d,cnt=0,ans=0; int head[200000],nxt[200000],to[200000],val[200000]; int f[50][110],h[100],dis[100],q[10000],v[110][110]; int dp[110]; void addedge(int x,int y,int z) { cnt++; nxt[cnt]=head[x]; head[x]=cnt; to[cnt]=y; val[cnt]=z; } int spfa(int x,int y) { memset(h,0,sizeof(h)); memset(dis,0x7f,sizeof(dis)); int l=0,r=1; q[1]=1,dis[1]=0,h[1]=1; while(l<r) { int u=q[++l]; for(int i=head[u];i!=-1;i=nxt[i]) { int v=to[i]; if(f[v][y]-f[v][x-1]) continue;//判断x-y天v码头是否会无法装载 if(dis[v]>dis[u]+val[i]) { dis[v]=dis[u]+val[i]; if(!h[v]) { h[v]=1; q[++r]=v; } } } h[u]=0; } return dis[m]; } int main() { memset(f,0,sizeof(f)); memset(v,0x7f,sizeof(v)); memset(dp,0x7f,sizeof(dp)); memset(head,-1,sizeof(head)); scanf("%d%d%d%d",&n,&m,&k,&e); for(int i=1;i<=e;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); addedge(x,y,z); addedge(y,x,z); } scanf("%d",&d); for(int i=1;i<=d;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); for(int j=y;j<=z;j++) f[x][j]=1; } for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) f[i][j]+=f[i][j-1];//做前缀和，方便spfa时判断 for(int i=1;i<=n;i++) for(int j=i;j<=n;j++) v[i][j]=spfa(i,j); dp[0]=0; for(int i=1;i<=n;i++) for(int j=0;j<i;j++) { if(v[j+1][i]==2139062143) continue;//如果i~j天没有不改变路线的方法就跳过，这个乱七八糟的值，时memset时候附上去的 dp[i]=min(dp[j]+v[j+1][i]*(i-j)+k,dp[i]); } printf("%d",dp[n]-k); return 0; } ```