BZOJ 1003: [ZJOI2006]物流運(yùn)輸trans DP+SPFA
來源：程序員人生 發(fā)布時(shí)間：2015-05-07 09:44:44 閱讀次數(shù)：2819次
dp[i]=min(dp[j]+dur[j+1][i]*(i-j)+K) dur(i,j)表示從i天到j(luò)天不換路的最短距離
1003: [ZJOI2006]物流運(yùn)輸trans
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 4001 Solved: 1671
[Submit][Status][Discuss]
Description
物流公司要把1批貨物從碼頭A運(yùn)到碼頭B。由于貨物量比較大，需要n天才能運(yùn)完。貨物運(yùn)輸進(jìn)程中1般要轉(zhuǎn)停好幾個(gè)碼頭。物流公司通常會設(shè)計(jì)1條固定的運(yùn)輸線路，以便對全部運(yùn)輸進(jìn)程實(shí)行嚴(yán)格的管理和跟蹤。由于各種因素的存在，有的時(shí)候某個(gè)碼頭會沒法裝卸貨物。這時(shí)候候就必須修改運(yùn)輸線路，讓貨物能夠按時(shí)到達(dá)目的地。但是修改線路是1件10分麻煩的事情，會帶來額外的本錢。因此物流公司希望能夠訂1個(gè)n天的運(yùn)輸計(jì)劃，使得總本錢盡量地小。
Input
第1行是4個(gè)整數(shù)n（1<=n<=100）、m（1<=m<=20）、K和e。n表示貨物運(yùn)輸所需天數(shù)，m表示碼頭總數(shù)，K表示每次修改運(yùn)輸線路所需本錢。接下來e行每行是1條航線描寫，包括了3個(gè)整數(shù)，順次表示航線連接的兩個(gè)碼頭編號和航線長度（>0）。其中碼頭A編號為1，碼頭B編號為m。單位長度的運(yùn)輸費(fèi)用為1。航線是雙向的。再接下來1行是1個(gè)整數(shù)d，后面的d行每行是3個(gè)整數(shù)P（
1 < P < m）、a、b（1 < = a < = b < = n）。表示編號為P的碼頭從第a天到第b天沒法裝卸貨物（含頭尾）。同1個(gè)碼頭有可能在多個(gè)時(shí)間段內(nèi)不可用。但任什么時(shí)候間都存在最少1條從碼頭A到碼頭B的運(yùn)輸線路。
Output
包括了1個(gè)整數(shù)表示最小的總本錢。總本錢=n天運(yùn)輸線路長度之和+K*改變運(yùn)輸線路的次數(shù)。
Sample Input
5 5 10 8
1 2 1
1 3 3
1 4 2
2 3 2
2 4 4
3 4 1
3 5 2
4 5 2
4
2 2 3
3 1 1
3 3 3
4 4 5
Sample Output
32
HINT
前3天走1⑷⑸，后兩天走1⑶⑸，這樣總本錢為(2+2)*3+(3+2)*2+10=32
Source
/* ***********************************************
Author :CKboss
Created Time :2015年04月30日 星期4 10時(shí)58分56秒
File Name :BZOJ1003.cpp
************************************************ */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long int LL;
const int maxn=1000;
const LL INF=0x3f3f3f3f3f3f3f3f;
int n,m,K,e,d;
struct Edge
{
int to,next,len;
}edge[maxn];
int Adj[50],Size;
void init()
{
memset(Adj,⑴,sizeof(Adj)); Size=0;
}
void add_edge(int u,int v,int len)
{
edge[Size].to=v; edge[Size].next=Adj[u];
edge[Size].len=len; Adj[u]=Size++;
}
void Add_Edge(int u,int v,int len) { add_edge(u,v,len); add_edge(v,u,len); }
bool go[50][200];
LL dur[200][200];
bool cango[50];
/*************spfa********************/
int dist[50],cq[50];
bool inq[50];
bool spfa()
{
memset(dist,63,sizeof(dist));
memset(cq,0,sizeof(cq));
memset(inq,false,sizeof(inq));
dist[1]=0; queue<int> q;
q.push(1); inq[1]=true; cq[1]=1;
while(!q.empty())
{
int u=q.front(); q.pop();
for(int i=Adj[u];~i;i=edge[i].next)
{
int v=edge[i].to;
int len=edge[i].len;
if(cango[v]==false) continue;
if(dist[v]>dist[u]+len)
{
dist[v]=dist[u]+len;
if(!inq[v])
{
inq[v]=true;
cq[v]++;
if(cq[v]>=m) return false;
q.push(v);
}
}
}
inq[u]=false;
}
return true;
}
LL dp[200];
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
init();
memset(go,true,sizeof(go));
scanf("%d%d%d%d",&n,&m,&K,&e);
for(int i=0;i<e;i++)
{
int u,v,l;
scanf("%d%d%d",&u,&v,&l);
Add_Edge(u,v,l);
}
scanf("%d",&d);
for(int i=0;i<d;i++)
{
int p,a,b;
scanf("%d%d%d",&p,&a,&b);
for(int j=a;j<=b;j++) go[p][j]=false;
}
for(int i=1;i<=n;i++)
{
for(int j=i;j<=n;j++)
{
memset(cango,true,sizeof(cango));
for(int k=1;k<=m;k++)
{
bool fg=true;
for(int l=i;l<=j&&fg;l++)
if(go[k][l]==false) fg=false;
if(fg==false) cango[k]=false;
}
spfa();
dur[i][j]=1LL*dist[m];
}
}
memset(dp,63,sizeof(dp));
dp[0]=0;dp[1]=dur[1][1];
for(int i=2;i<=n;i++)
{
if(dur[1][i]!=INF) dp[i]=dur[1][i]*i;
for(int j=1;j+1<=i;j++)
{
if(dur[j+1][i]==INF) continue;
dp[i]=min(dp[i],dp[j]+dur[j+1][i]*(i-j)+K);
}
}
printf("%lld
",dp[n]);
return 0;
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈
