SRM 477 DIV1 1000
题意：给定一棵树，最多可给这棵树增加k条捷径，每条捷径长度为L，且只能走一次，问从0出发回到0遍历所有的边需要走的最短距离。
树型dp，状态为dp[i][j][2]。
dp[i][j][0]表示从i出发，用了j次捷径，遍历完下面所有边且最后走的路径到底后没有回来的最小距离。
dp[i][j][1]表示从i出发，用了j次捷径，遍历完下面所有边且回到i的最小距离。
转移看代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
using namespace std ;
typedef long long ll ;
const double eps = 1e-6 ;
const int inf = 1e8;
vector<int> ev[205],ew[205];
int dp[205][105][2],p[105][2];
string s = "";
int K,L;
class KingdomTour
{
public:
void dfs(int u,int f){
for(int i=0;i<=K;i++) dp[u][i][0] = dp[u][i][1] = 0;
for(int i=0;i<(int)ev[u].size();i++){
int v = ev[u][i];
int w = ew[u][i];
if(v==f) continue;
dfs(v,u);
for(int i=0;i<=K;i++) p[i][0] = p[i][1] = inf;
for(int i=0;i<=K;i++)
for(int j=0;j<=K;j++)
if(i+j<=K){
Min(p[i+j+1][0],dp[u][i][0]+dp[v][j][0]+L+w);
//之前有儿子节点不回来， v最后通过捷径回到u
Min(p[i+j][0],dp[u][i][0]+dp[v][j][1]+2*w);
//之前有儿子节点不回来， v直接走回到u
Min(p[i+j][0],dp[u][i][1]+dp[v][j][0]+w);
//之前没有儿子节点不回来，v不回到u
Min(p[i+j][1],dp[u][i][1]+dp[v][j][1]+2*w);
//之前没有儿子节点不回来，v直接走回到u
Min(p[i+j+1][1],dp[u][i][1]+dp[v][j][0]+w+L);
//之前没有儿子节点不回来，v最后通过捷径回到u
Min(p[i+j+1][1],dp[u][i][0] + dp[v][j][0]+L+w);
//之前有儿子节点不回来，直接走到当前儿子叶子节点走回来。
}
for(int i=0;i<=K;i++){
dp[u][i][0] = p[i][0];
dp[u][i][1] = p[i][1];
}
}
}
void get(int &w,int &i){
w = 0;
while(i<(int)s.size() && s[i]<='9' && s[i]>='0'){
w = w*10 +s[i]-'0';
i++;
}
i++;
}
int minTime(int N, vector <string> roads, int K, int L){
::K = K;
::L = L;
s = "";
for(int i=0;i<(int)roads.size();i++) s += roads[i];
for(int i=0;i<N;i++) ev[i].clear(),ew[i].clear();
int l = 0;
while(1){
int u,v,w;
get(u,l);
get(v,l);
get(w,l);
ev[u].push_back(v);ew[u].push_back(w);
ev[v].push_back(u);ew[v].push_back(w);
if(l>=(int)s.size()) break;
}
dfs(0,0);
int ans = inf;
for(int i=0;i<=K;i++) ans = min(ans,dp[0][i][1]);
return ans;
}
};
// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor