1003: [ZJOI2006]物流運輸trans
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 2099 Solved: 829
[Submit][Status][Discuss]
Description
物流公司要把一批貨物從碼頭A運到碼頭B。由於貨物量比較大，需要n天才能運完。貨物運輸過程中一般要轉停好幾個碼頭。物流公司通常會設計一條固定的運輸路線，以便對整個運輸過程實施嚴格的管理和跟蹤。由於各種因素的存在，有的時候某個碼頭會無法裝卸貨物。這時候就必須修改運輸路線，讓貨物能夠按時到達目的地。但是修改路線是一件十分麻煩的事情，會帶來額外的成本。因此物流公司希望能夠訂一個n天的運輸計劃，使得總成本盡可能地小。
Input
第一行是四個整數n（1<=n<=100）、m（1<=m<=20）、K和e。n表示貨物運輸所需天數，m表示碼頭總數，K表示每次修改運輸路線所需成本。接下來e行每行是一條航線描述，包括了三個整數，依次表示航線連接的兩個碼頭編號以及航線長度（>0）。其中碼頭A編號為1，碼頭B編號為m。單位長度的運輸費用為1。航線是雙向的。 再接下來一行是一個整數d，後面的d行每行是三個整數P（ 1 < P < m）、a、b（1 < = a < = b < = n）。表示編號為P的碼頭從第a天到第b天無法裝卸貨物（含頭尾）。同一個碼頭有可能在多個時間段內不可用。但任何時間都存在至少一條從碼頭A到碼頭B的運輸路線。
Output
包括了一個整數表示最小的總成本。總成本=n天運輸路線長度之和+K*改變運輸路線的次數。
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
Sample Output
32
HINT
前三天走1-4-5，後兩天走1-3-5，這樣總成本為(2+2)*3+(3+2)*2+10=32
這題咋看不好做……
實際上暴力都能過……
暴力枚舉第i天到第j天（不改線路）的最小費用
然後n^2暴力……這樣也能過……
FJ某年OI既視感
[cpp]
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<cctype>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define RepD(i,n) for(int i=n;i>=0;i--)
#define MAXD (10000+10)
#define MAXM (800+10)
#define MAXN (20+10)
#define MAXDay (100+10)
#define INF (2139062143)
int n,m,k,day,ud;
struct comm
{
int no,x,y;
friend bool operator<(comm a,comm b){return a.x<b.x;}
}ask[MAXD];
int edge[MAXM],next[MAXM]={0},pre[MAXN]={0},weight[MAXM],size=0;
bool b[MAXN]={0};
void addedge(int u,int v,int w)
{
edge[++size]=v;
weight[size]=w;
next[size]=pre[u];
pre[u]=size;
}
int q[MAXN*8],d[MAXN];
void SPFA(int day1,int day2)
{
memset(b,0,sizeof(b));
memset(d,127,sizeof(d));
For(i,ud) if (!(ask[i].y<day1||ask[i].x>day2)) b[ask[i].no]=1;
int head=1,tail=1;d[q[1]=1]=0;
while (head<=tail)
{
int now=q[head];
Forp(now)
{
int v=edge[p];
if (!b[v]&&d[v]>d[now]+weight[p])
{
d[v]=d[now]+weight[p];
q[++tail]=v;
}
}
head++;
}
}
int f[MAXN];
int main()
{
// freopen("bzoj1003.in","r",stdin);
scanf("%d%d%d%d",&day,&n,&k,&m);
For(i,m) {int u,v,w;scanf("%d%d%d",&u,&v,&w);addedge(u,v,w),addedge(v,u,w);}
scanf("%d",&ud);For(i,ud) scanf("%d%d%d",&ask[i].no,&ask[i].x,&ask[i].y);
f[0]=0;
For(i,day)
{
f[i]=INF;
Rep(j,i)
{
SPFA(j+1,i);
if (d[n]==INF) continue;
else f[i]=min(f[i],f[j]+(i-j)*d[n]+k);
}
}
printf("%d",f[day]-=k);
return 0;
}
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<cctype>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define RepD(i,n) for(int i=n;i>=0;i--)
#define MAXD (10000+10)
#define MAXM (800+10)
#define MAXN (20+10)
#define MAXDay (100+10)
#define INF (2139062143)
int n,m,k,day,ud;
struct comm
{
int no,x,y;
friend bool operator<(comm a,comm b){return a.x<b.x;}
}ask[MAXD];
int edge[MAXM],next[MAXM]={0},pre[MAXN]={0},weight[MAXM],size=0;
bool b[MAXN]={0};
void addedge(int u,int v,int w)
{
edge[++size]=v;
weight[size]=w;
next[size]=pre[u];
pre[u]=size;
}
int q[MAXN*8],d[MAXN];
void SPFA(int day1,int day2)
{
memset(b,0,sizeof(b));
memset(d,127,sizeof(d));
For(i,ud) if (!(ask[i].y<day1||ask[i].x>day2)) b[ask[i].no]=1;
int head=1,tail=1;d[q[1]=1]=0;
while (head<=tail)
{
int now=q[head];
Forp(now)
{
int v=edge[p];
if (!b[v]&&d[v]>d[now]+weight[p])
{
d[v]=d[now]+weight[p];
q[++tail]=v;
}
}
head++;
}
}
int f[MAXN];
int main()
{
// freopen("bzoj1003.in","r",stdin);
scanf("%d%d%d%d",&day,&n,&k,&m);
For(i,m) {int u,v,w;scanf("%d%d%d",&u,&v,&w);addedge(u,v,w),addedge(v,u,w);}
scanf("%d",&ud);For(i,ud) scanf("%d%d%d",&ask[i].no,&ask[i].x,&ask[i].y);
f[0]=0;
For(i,day)
{
f[i]=INF;
Rep(j,i)
{
SPFA(j+1,i);
if (d[n]==INF) continue;
else f[i]=min(f[i],f[j]+(i-j)*d[n]+k);
}
}
printf("%d",f[day]-=k);
return 0;
}
