I have a graph where each node has a numeric value. Starting from a node of my choice, I have to find the path where the sum of the node values is the heaviest. However I can only cross the same bridge once BUT it is possible to pass several times on the same node.
For example if I have a undirected graph like this:
EDGES
0 1
0 2
0 3
1 2
1 4
and each node have a weight like this:
Node weight
0 -> 4
1 -> 3
2 -> 7
3 -> 2
4 -> 9
If I start from the source "1", the path's output should be like this 1->2->0->1->4 with total weight of 23.
I'm trying to solve this problem with DFS in this way:
int dfs(vector<vector<int> >& g, int* cost, int u, int pre)
{
vis[u] = true;
dp[u] = cost[u];
bool check = 1;
int cur = cost[u];
for (auto& x : g[u]) {
if (vis[x] && x != pre) {
check = 0;
} else if (!vis[x]) {
check &= dfs(g, cost, x, u);
cur = max(cur, cost[u] + dp[x]);
}
}
dp[u] = cur;
if (!check) {
canTake += cost[u];
} else {
best = max(best, dp[u]);
}
return check;
}
int FindMaxCost(vector<vector<int> >& g,int* cost, int source)
{
dfs(g, cost, source, -1);
cout << canTake + best;
}
With this I can find the right total weight but I don't know how to save the right path.
I'm trying to take the path picking u-node in this code:
if (!check) {
canTake += cost[u];
// taking the u-node
} else {
best = max(best, dp[u]);
// taking here the last node in global variable
}
but the path is not correct.