BZOJ 1003: [ZJOI2006]物流运输trans
Fancy
posted @ 2015年7月19日 23:42
in BZOJ
, 308 阅读
题目大意:物流公司要把一批货物从码头A运到码头B。由于货物量比较大,需要n天才能运完。货物运输过程中一般要转停好几个码头。物流公司通常会设计一条固定的运输路线,以便对整个运输过程实施严格的管理和跟踪。由于各种因素的存在,有的时候某个码头会无法装卸货物。这时候就必须修改运输路线,让货物能够按时到达目的地。但是修改路线是一件十分麻烦的事情,会带来额外的成本。因此物流公司希望能够订一个n天的运输计划,使得总成本尽可能地小。
SPFA+DP
g[j]=min(g[j],g[i-1]+SPFA(i,j)*(j-i+1)+K)
n呀m呀,傻傻分不清楚。。。
#include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<queue> using namespace std; vector<int> to[31],cost[31]; queue<int> q; int ds[31],n,m,day,K,num,f[110][110],g[110],h[31]; bool vis[31]; int SPFA() { memset(ds,0x7f,sizeof(ds)); ds[1]=0; vis[1]=1; q.push(1); while(!q.empty()) { int x=q.front(); q.pop(); vis[x]=0; for(int i=0;i<to[x].size();i++) { int y=to[x][i],c=cost[x][i]; if(ds[y]>ds[x]+c) { ds[y]=ds[x]+c; if(!vis[y]) { vis[y]=1; q.push(y); } } } } if(ds[n]<ds[0]) return ds[n]; return -1; } int main() { scanf("%d%d%d%d",&day,&n,&K,&m); for(int i=1,x,y,z;i<=m;i++) { scanf("%d%d%d",&x,&y,&z); to[x].push_back(y); cost[x].push_back(z); to[y].push_back(x); cost[y].push_back(z); } scanf("%d",&m); for(int i=1,x,y,z;i<=m;i++) { scanf("%d%d%d",&x,&y,&z); for(int j=y;j<=z;j++) f[j][++f[j][0]]=x; } memset(g,0x7f,sizeof(g)); g[0]=0; for(int i=1;i<=day;i++) { memset(vis,0,sizeof(vis)); for(int j=i;j<=day;j++) { for(int t=1;t<=f[j][0];t++) vis[f[j][t]]=1; num=SPFA(); if(num==-1) break; g[j]=min(g[j],g[i-1]+num*(j-i+1)+K); } } printf("%d\n",g[day]-K); }