M - 酱神的旅行
Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
酱神要去一棵树上旅行。
酱神制定了一个旅行计划，他要按顺序去m个树上的结点，a1,a2,a3,...,am。
酱神有一辆车，树上的每一条边既可以开车通过，也可以走过去，两种方法需要不同的时间。如果选择走路，酱神需要先把车停在结点上，在他下一次要开车的时候，必须先回到停车的结点取车。
酱神和他的爱车一开始都在a1结点上，酱神要依次访问完这m个结点最少需要多少时间。
Input
第一行两个数n,m。
1=<n,m<=5000
接下来n−1行，每行4个数，u,v,walk,drive。表示结点u和结点v之间有一条走路耗时为walk，开车耗时为drive的边。
1=<u,v<=n
1=<walk,drive<=109
最后输入m个数，a1,a2,a3,...,am， 酱神要按顺序访问的结点。
1=<ai<=n
Output
输出一个数，酱神的最小耗时。
Sample input and output
| Sample Input | Sample Output |
|---|---|
2 2 1 2 3 100 1 2 |
3 |
4 4 1 2 1 20 3 2 100 1 2 4 1 100 1 2 3 4 |
23 |
解题报告:
注意到树上两个点之间的路径是唯一的，且访问点的顺序是固定的，也就是说，经过的点的顺序是固定的，于是我们不妨令
dp(i , j )表示在路径在的第 i 个点，且是否有车的最小花费( 0 -> 无车 ， 1 -> 有车 )
dp(cur , 0 ) = min ( dp( cur^1 , 0 ) , dp( cur^1 , 1 ) ) + walk_cost( i -> i + 1) )
è 直接走路过来 / 把车停在上一个点
dp(cur , 1 ) = min ( dp( cur^1 , 1 ) + car_cost(i -> i + 1) , f[r] + sum[i] ) -> r = a[i]
-> 直接开车过来 / 原来车就停在这，现在回来取（维护走路长度的前缀和）
-> f[r] = min( f[r] , dp(cur , 1) - sum[ cur ^ 1 ] );
注意到本题时限的原因，每次调用无根树转有根树时，需用BFS实现
若需要进一步降低时限，可使用LCA的离线算法，可将复杂度降低至O(N + Q),求路径上的点就不再累述.
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #define pb push_back typedef long long ll; const int maxn = 5e3 + 50; const ll inf = 999999999999999999; using namespace std; int n,m,prenode[maxn],cur = 0,h[maxn],passnode[maxn],size,pretarget,target; ll dp[2][2],f[maxn],sum[2],walkdis[maxn],cardis[maxn]; typedef struct Edge { int target,walk,drive; Edge(const int & target, const int & walk , const int & drive) { this->target = target , this->walk = walk , this->drive = drive; } }; vector<Edge>E[maxn]; typedef struct status { int pos,fat; }; //无根树转有根树，BFS实现（比递归快 20 % ) inline void init_prenode(int pos) { status q[maxn*2]; register int front = 0 , rear = 0; q[rear].pos = pos , q[rear++].fat = 0 ; while(front < rear) { int thispos = q[front].pos; int thisfat = q[front].fat; prenode[thispos] = thisfat; for(int i = 0 ; i < E[thispos].size() ; ++ i) { int nextnode = E[thispos][i].target; if (nextnode != thisfat) { if (prenode[nextnode] == thispos) continue; //剪枝 q[rear].pos = nextnode , q[rear++].fat = thispos; } else walkdis[thisfat] = E[thispos][i].walk , cardis[thisfat] = E[thispos][i].drive; } ++front; } } inline void add_nodes() { int k = prenode[pretarget]; while(k) { passnode[size++] = k; k = prenode[k]; } } int main(int argc,char *argv[]) { int st; scanf("%d%d",&n,&m); for(int i = 0 ; i < n - 1 ; ++ i) { int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d); E[a].pb(Edge(b,c,d)); E[b].pb(Edge(a,c,d)); } for(int i = 1 ; i <= 5000 ; ++ i) f[i] = inf; memset(dp,0,sizeof(dp)); memset(sum,0,sizeof(sum)); memset(prenode,0,sizeof(prenode)); memset(cardis,0,sizeof(cardis)); memset(walkdis,0,sizeof(walkdis)); size = 0; dp[cur][0] = inf; dp[cur][1] = 0; if (m == 1) { printf("0 "); return 0; } scanf("%d",&pretarget); init_prenode(pretarget); for(int times = 1 ; times < m ; ++ times) { scanf("%d",&target); size = 0; init_prenode(target); add_nodes(); for(int i = 0 ; i < size ; ++ i) { cur ^= 1; int r = passnode[i]; sum[cur] = sum[cur^1] + walkdis[r]; dp[cur][0] = min(dp[cur^1][0] , dp[cur^1][1]) + walkdis[r]; dp[cur][1] = min( dp[cur^1][1] + cardis[r] , f[r] + sum[cur]); f[r] = min(f[r] , dp[cur][1] - sum[cur]); } pretarget = target; } printf("%lld ",min(dp[cur][0],dp[cur][1])); return 0; }