城市规划

题目描述

有一座城市，城市中有 $N$ 个公交站，公交站之间通过 $N-1$ 条道路连接，每条道路有相应的长度。保证所有公交站两两之间能够通过唯一的通路互相达到。
两个公交站之间路径长度定义为两个公交站之间路径上所有边的边权和。
现在要对城市进行规划，将其中 $M$ 个公交站定为“重要的”。
现在想从中选出 $K$ 个节点，使得这 $K$ 个公交站两两之间路径长度总和最小。输出路径长度总和即可（节点编号从 $1$ 开始）。

输入格式

第 $1$ 行包含三个正整数 $N, M$ 和 $K$ 分别表示树的节点数，重要的节点数，需要选出的节点数。
第 $2$ 行包含 $M$ 个正整数，表示 $M$ 个重要的节点的节点编号。
接下来 $N-1$ 行，每行包含三个正整数 $a, b, c$，表示编号为 $a$ 的节点与编号为 $b$ 的节点之间有一条权值为 $c$ 的无向边。每行中相邻两个数之间用一个空格分隔。

输出格式

输出只有一行，包含一个整数表示路径长度总和的最小值。

样例输入

5 3 2
1 3 5
1 2 4
1 3 5
1 4 3
4 5 1

样例输出

4

样例解释

样例中的树如上图所示。
重要的节点标号为 1, 3, 5，从中选出两个点，有三种方案:
方案 1: 1, 3 之间路径长度为 5
方案 2: 1, 5 之间路径长度为 4
方案 3: 3, 5 之间路径长度为 9

数据规模与子任务

对于所有的数据，$1≤a,b≤N，c≤10^5，M≤N，K≤M$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAXN 200005
ll n, m, k, t, a, b, c, dp[MAXN][105], ans = 0x3f3f3f3f3f3f3f3f;
struct edge {
    ll u, v, w, next;
} e[MAXN];

ll tot = 0;
vector<ll> head(MAXN, -1);
void addEdge(ll u, ll v, ll w) {
    e[tot].u = u;
    e[tot].v = v;
    e[tot].w = w;
    e[tot].next = head[u];
    head[u] = tot++;
}

void dfs(ll u, ll fa) {
    for (ll i = head[u]; i != -1; i = e[i].next) {
        ll v = e[i].v;
        if (v == fa)
            continue;
        dfs(v, u);
        for (ll j = k; j >= 0; j--) {
            for (ll l = 0; l <= j; l++) {
                dp[u][j] = min(dp[u][j], dp[v][l] + dp[u][j - l] + l * (k - l) * e[i].w);
            }
        }
    }
    ans = min(ans, dp[u][k]);
}

int main() {
    memset(dp, 0x3f, sizeof(dp));
    cin >> n >> m >> k;
    for (ll i = 1; i <= m; i++) {
        cin >> t;
        dp[t][1] = 0;
    }
    for (ll i = 1; i <= n; i++) {
        dp[i][0] = 0;
    }
    for (ll i = 1; i < n; i++) {
        cin >> a >> b >> c;
        addEdge(a, b, c);
        addEdge(b, a, c);
    }
    dfs(1, 0);
    cout << ans;
    return 0;
}