Maximum Value Path in a Graph

Moderate

0/80

0 upvote

Problem statement

You are given a directed graph with N nodes (numbered 0 to N-1), where each node has an integer value. You are also given an integer k.

You can start your journey at any node in the graph. From your current node, you can move to any of its neighbors by following a directed edge. Each move takes one step. You are allowed to perform at most k moves.

Each time you visit a node (including your starting node), you collect its value. You are allowed to visit the same node multiple times, and its value is added to your total each time you visit.

Your task is to find the maximum possible total value you can accumulate after a path of at most k moves.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains three space-separated integers: N (number of nodes), M (number of directed edges), and k (maximum number of moves).

The second line contains N space-separated integers, representing the values of nodes 0 to N-1.

The next M lines each contain two space-separated integers u and v, representing a directed edge from node u to node v.

Output Format:

Your function should return a single long integer representing the maximum possible total value. The runner code will handle printing.

Notes:

This problem can be solved efficiently using dynamic programming. Let dp[i][j] be the maximum value of a path of exactly i moves ending at node j. The state transition would be:

dp[i][j] = value[j] + max(dp[i-1][p]) for all nodes p that have an edge leading to j.

The base case is dp[0][j] = value[j] for all j. The final answer will be the maximum value found anywhere in the dp table.

Sample Input 1:

Sample Output 1:

Explanation for Sample 1:

The graph is 0(10) -> 1(20) -> 2(5). We have at most k=2 moves.
  Start at node 0, 2 moves: 0 -> 1 -> 2. Path values: 10, 20, 5. Total = 35.
  Start at node 1, 1 move: 1 -> 2. Path values: 20, 5. Total = 25.
  Start at node 2, 0 moves: 2. Path value: 5.
The maximum possible value is 35.

Sample Input 2:

Sample Output 2:

Explanation for Sample 2:

The graph is 0(10) -> 1(1) and 1(1) <-> 2(100). We have at most k=3 moves.
  The optimal path starts at node 2.
  Path: 2 -> 1 -> 2 -> 1

Moves: 3 Values collected: 100 (start) + 1 (move 1) + 100 (move 2) + 1 (move 3) = 202.

Expected Time Complexity:

The expected time complexity is O(k* (N+M)).

Constraints:

1 <= N, k <= 1000
0 <= M <= 5000
0 <= u, v < N
0 <= Node Value <= 10^9

Approaches (1)

Approach 1

Dynamic Programming

Time Complexity

Space Complexity

(100% EXP penalty)

Maximum Value Path in a Graph

Console