61.187.179.132:8080/JudgeOnline/showproblem

[ZJOI2006]物流运输trans

Time Limit:10000MS  Memory Limit:165536K
Total Submit:91 Accepted:33
Case Time Limit:1000MS

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

Source

好像是老题目了。。以前在VJ上看到过。不过我是第一次做。。还有就是我刚刚实在太无聊了。。把自己以前在PKU上过的USACO月赛题目交题库了。。结果刷了不少Rank。。其实都是USACO的水题囧。。PKU居然有代码打包的功能的，真是太强了了Orz。。
这道题目的话设Dp(i)表示1到i天最小费用，那么Dp(i)=Min(Dp(j)+Cost(j+1,i)*(i-j)+k)..Cost(l,r)表示l到r期间都可用的最短路线长度。。每次都spfa一次就可以了。。反正数据这么小想怎么做都可以囧。。
最后再-个k就OK了。。
Code：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<vector>
#include<set>
#include<queue>
#include<map>
#define rep(i,n) for(int i=0;i<n;i++)
#define For(i,a,b) for(int i=a;i<=b;i++)
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
const int inf=~0U>>2,maxT=100+1,maxn=20,maxm=1000;
int T,n,k,m;
struct Edge
{
int t,c;
Edge*next;
Edge(int _t,int _c,Edge*_n):t(_t),c(_c),next(_n){}
}*E[maxn]={0};
struct Vertex
{
int D[maxT];
Vertex(){memset(D,0,sizeof(D));}
void Ins(int l,int r)
{
For(i,l,r) D[i]=1;
}
void Set()
{
For(i,1,T) D[i]+=D[i-1];
}
bool ok(int l,int r)
{
return D[r]==D[l-1];
}
}V[maxn];
void InsEdge(int s,int t,int c)
{
E[s]=new Edge(t,c,E[s]);
E[t]=new Edge(s,c,E[t]);
}
void Init()
{
cin>>T>>n>>k>>m;int s,t,c;
while(m–)
{
scanf("%d %d %d",&s,&t,&c);
InsEdge(s-1,t-1,c);
}
int p,a,l,r;cin>>p;
while(p–)
{
scanf("%d %d %d",&a,&l,&r);
V[a-1].Ins(l,r);
}
rep(i,n)V[i].Set();
}
int Cost(int l,int r)
{
static int dist[maxn];
static bool inq[maxn];
rep(i,n) dist[i]=inf,inq[i]=false;
queue<int> Q;
Q.push(0);inq[0]=true;dist[0]=0;
while(Q.size())
{
int t=Q.front();Q.pop();inq[t]=false;int cost=dist[t];
for(Edge*e=E[t];e;e=e->next)
{
int ncost=cost+e->c,v=e->t;
if(!V[v].ok(l,r))continue;
if(dist[v]>ncost)
{
dist[v]=ncost;
if(!inq[v]) Q.push(v),inq[v]=true;
}
}
}
return dist[n-1];
}
int dp[maxT];
void Work()
{
dp[0]=0;
For(i,1,T)
{
dp[i]=inf;
for(int j=i-1;j>=0;–j)
{
int c=Cost(j+1,i);
if(c==inf)break;
dp[i]=min(dp[i],dp[j]+c*(i-j)+k);
}
}
cout<<dp[T]-k<<endl;
}
int main()
{
//freopen("in","r",stdin);
Init();
Work();
}