- #include
- #include
- #include
- #include
- #include
- #include #defineIOS ios::sync_with_stdio(false)using namespace std;
- #defineinf (0x3f3f3f3f)
- typedef long long int LL;
- #include
- #include
- #include
- #include <set>
- #include
- #include
- #include <string>
- #include
- const intmaxn = 1e2 +20;
- int Lchild[maxn], Rchild[maxn], dp[maxn][maxn][maxn];
- int a[maxn], fa[maxn], len[maxn];
- intdfs(intcur,inthasPoint,intk,int dis) {
- if(cur == -1|| hasPoint == -1)return 0;
- if(dp[cur][hasPoint][k] != inf)return dp[cur][hasPoint][k];
- int&now = dp[cur][hasPoint][k];//引用改值
- for(inti =0; i <= k; ++i) {//这个cur节点不做中转站。now = min(now, dfs(Lchild[cur], hasPoint, i, dis + len[cur]) + dfs(Rchild[cur], hasPoint, k - i, dis) + a[cur] * (dis + len[cur]));
- }
- for(inti =0; i < k; ++i) {// 这个点用来中转now = min(now, dfs(Lchild[cur], cur, i,0) + dfs(Rchild[cur], hasPoint, k - i -1, dis));
- }
- return dp[cur][hasPoint][k];
- }
- void work() {
- int n, k;
- cin >> n >> k;
- memset(dp, 0x3f,sizeof dp);
- memset(Lchild, -1,sizeof Lchild);
- memset(Rchild, -1,sizeof Rchild);
- for(inti =1; i <= n; ++i) {
- cin >> a[i] >> fa[i] >> len[i];
- Rchild[i] = Lchild[fa[i]];
- Lchild[fa[i]] = i;
- }
- cout << dfs(0,0, k,0) << endl;
- }
- int main() {
- #ifdef local
- freopen("data.txt","r", stdin);
- // freopen("data.txt", "w", stdout);
- #endif
- work();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-1977788.html