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 96 97 98 99 100 101 102 103 104 105
|
#pragma GCC optimize(2) #pragma GCC optimize(3, "Ofast", "inline") #include<bits/stdc++.h> using namespace std;
typedef long long ll; typedef __int128 int128;
namespace FastIO { char buf[1 << 20], *p1, *p2; #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++) template<typename T> inline T read(T& x) { x = 0; int f = 1; char ch; while (!isdigit(ch = getchar())) if (ch == '-') f = -1; while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar(); x *= f; return x; } template<typename T, typename... Args> inline void read(T& x, Args &...x_) { read(x); read(x_...); return; } inline ll read() { ll x; read(x); return x; } inline void read(char *s) { scanf("%s", s + 1); } }; using namespace FastIO;
const int N = 1e4 + 10;
struct Edge { int to, nt, wt; Edge() {} Edge(int to, int nt, int wt) : to(to), nt(nt), wt(wt) {} }e[N << 1]; int hd[N], cnte; void AddEdge(int u, int v, int w) { e[++cnte] = Edge(v, hd[u], w); hd[u] = cnte; }
int n, s, K;
ll dp[N][20];
inline void Input() { read(n, s, K); int u, v, w; for(int i = 1; i <= n; i++) { read(u, v, w); AddEdge(u, v, w); AddEdge(v, u, w); } }
inline void Dfs(int u, int fa) { for(int i = hd[u]; i ; i = e[i].nt) { int v = e[i].to; if(v == fa) continue; Dfs(v, u); for(int j = K; j >= 0; j--) { dp[u][j] += dp[v][0] + 2 * e[i].wt; for(int k = 1; k <= j; k++) { dp[u][j] = min(dp[u][j], dp[u][j - k] + dp[v][k] + k * e[i].wt); } } } }
inline void Work() { Dfs(s, s); printf("%lld", dp[s][K]); }
int main() { int T = 1; while(T--) { Input(); Work(); } return 0; }
|