I am given an bidirectional weighted tree with n
nodes (root at 1
). I am supposed to implement an algorithm which can find the total weight of the heaviest path from root to leaf.
Here is what I have implemented (not working for hidden test cases) :
void dfs(std::vector<std::map<int, int>> &adj, std::vector<bool> &visited, int &max_len, int src = 1, int prev_len = 0) {
visited[src] = true;
int curr_len = 0;
for (auto &i : adj[src]) {
if (not visited[i.first]) {
curr_len = prev_len + i.second;
dfs(adj, visited, max_len, i.first, curr_len);
}
max_len = max(max_len, curr_len);
curr_len = 0;
}
}
int longestPath(std::vector<std::map<int, int>> &adj) {
int max_len = 0;
std::vector<bool> visited(adj.size());
dfs(adj, visited, max_len);
return max_len;
}
Tree is constructed using the following method:
void addEdge(std::vector<std::map<int, int>> &adj, int u, int v, int w = 0) {
adj[u][v] = w;
adj[v][u] = w;
}
Driver function:
signed main() {
int n, u, v, w;
std::cin >> n;
std::vector<std::map<int, int>> adj(n + 1);
for (int i = 0; i < n - 1; ++i) {
std::cin >> u >> v >> w;
addEdge(adj, u, v, w);
}
std::cout << longestPath(adj);
return 0;
}
What am I doing wrong here?
Aucun commentaire:
Enregistrer un commentaire