Dynamic Content Propagation with Hop Constraints
In Sharechat's vast social network, content needs to propagate efficiently from creators to users. However, simply reaching a user isn't enough; the 'cost' or 'latency' of propagation through various intermediary nodes (e.g., re-shares, algorithmic boosts) can vary. Furthermore, content often has a 'shelf life' or a maximum 'viral distance' it can travel before losing relevance, implying a limit on the number of hops it can take. This problem challenges you to find the most efficient propagation path under such constraints.
Given a directed graph representing a social network where nodes are users and edges represent potential content propagation channels (e.g., A shares to B), each with an associated latency. You need to find the minimum total latency for content to travel from a source user to a target user, adhering to a strict limit on the maximum number of hops (edges) the content can traverse.
Implement the function findMinPropagationLatency that takes the network details, source, target, and maximum hops, and returns the minimum total latency. If no path exists within the given maxHops, return -1.
Function Signature:
function findMinPropagationLatency(n: number, edges: number[][], source: number, target: number, maxHops: number): number
n: An integer representing the total number of users (nodes) in the network, indexed from 0 to n-1.edges: An array of arrays, where each inner array [u, v, latency] represents a directed edge from user u to user v with a propagation latency (cost).source: An integer representing the starting user's ID.target: An integer representing the destination user's ID.maxHops: An integer representing the maximum number of edges allowed in the propagation path.number. Return -1 if the target user cannot be reached from the source user within maxHops.u == v) or multiple edges between the same pair of nodes. If multiple edges exist, content can only use one at a time, but the algorithm should consider all options.source is the same as target, the latency is 0 if maxHops >= 0. This counts as 0 hops.target is unreachable, return -1.latency values are non-negative integers.0 to n-1.Examples
Example 1
Input:
n = 3, edges = [[0,1,10],[1,2,20],[0,2,5]], source = 0, target = 2, maxHops = 1
Output:
5
Note:
From user 0 to 2:
Example 2
Input:
n = 4, edges = [[0,1,1],[0,2,5],[1,3,1],[2,3,1]], source = 0, target = 3, maxHops = 2
Output:
2
Note:
From user 0 to 3:
Example 3
Input:
n = 3, edges = [[0,1,10],[1,2,20]], source = 0, target = 2, maxHops = 1
Output:
-1
Note:
From user 0 to 2:
Example 4
Input:
n = 2, edges = [[0,1,10]], source = 0, target = 0, maxHops = 0
Output:
0
Note:
Source is target, 0 hops, latency is 0. This is allowed by maxHops = 0.
Constraints
1 <= n <= 10000 <= edges.length <= 10000edges[i].length == 30 <= u, v < n1 <= latency <= 1000 (for each edge)0 <= source, target < n0 <= maxHops < nsource == target, unreachable targets, or maxHops = 0.Loading editor...