Submission #1213596

#TimeUsernameProblemLanguageResultExecution timeMemory
1213596Ghulam_JunaidPaths (RMI21_paths)C++20
0 / 100
0 ms324 KiB
#include <bits/stdc++.h> using namespace std; const int N = 2005; int n, k, par[N], mark[N], d[N]; vector<pair<int, int>> g[N]; void dfs(int v, int p = 0){ for (auto [w, u] : g[v]){ if (u == p) continue; par[u] = v; d[u] = d[v] + w * (!mark[u]); dfs(u, v); } } int main(){ cin >> n >> k; for (int i = 0; i < n - 1; i ++){ int u, v, w; cin >> u >> v >> w; g[u].push_back({w, v}); g[v].push_back({w, u}); } for (int v = 1; v <= n; v ++){ memset(mark, 0, sizeof mark); d[v] = 0; int ans = 0; for (int i = 0; i < k; i ++){ dfs(v); int u = 1; for (int j = 1; j <= n; j ++) if (d[u] < d[j]) u = j; ans += d[u]; while (1){ mark[u] = 1; if (u == v) break; u = par[u]; } } cout << ans << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...