In a C3 AI pipeline dependency graph, each directed edge (u, v, w) means task u can trigger task v with impact score w. Given a graph, a start node, an end node, and an integer k, return the top k highest-scoring simple paths from start to end, ordered by total score descending.
A path is simple, meaning it cannot visit the same node more than once. The score of a path is the sum of its edge weights.
Implement a function that takes:
n: number of nodes labeled 0 to n - 1edges: list of directed edges [from_node, to_node, weight]start: starting nodeend: destination nodek: number of paths to returnReturn a list of up to k paths, where each path is represented as [total_score, [node0, node1, ...]].
Example 1
Input: n = 5, edges = [[0,1,3],[0,2,2],[1,3,4],[2,3,5],[3,4,1],[1,4,6]], start = 0, end = 4, k = 3
Output: [[10,[0,1,4]],[8,[0,2,3,4]],[8,[0,1,3,4]]]
Explanation: The highest-scoring simple path is 0 -> 1 -> 4 with score 9? No, it is 3 + 6 = 9; the other two paths score 2 + 5 + 1 = 8 and 3 + 4 + 1 = 8. So the correct ordered output is [[9,[0,1,4]],[8,[0,2,3,4]],[8,[0,1,3,4]]].
Example 2
Input: n = 3, edges = [[0,1,2],[1,2,3],[0,2,1]], start = 0, end = 2, k = 2
Output: [[5,[0,1,2]],[1,[0,2]]]
Explanation: There are exactly two simple paths from 0 to 2.
1 <= n <= 150 <= len(edges) <= 600 <= from_node, to_node < n-10^4 <= weight <= 10^40 <= start, end < n1 <= k <= 20