FastPrep

Description

Solutions

Minimize Path Value

🤘 INTERN📚RELATED PROBLEMS

There is a weighted undirected graph with N nodes and M edges. The stress level of a path between two nodes is defined as the weight of the edge with the maximum value present in the path. Given a source node "source" and a destination node "destination", find a path with the minimum stress level. If no such path exists, report -1.

Function Description

Complete the function leastStressfulPath in the editor below.

leastStressfulPath has the following parameter(s):

int graph_nodes: number of nodes
int graph_from[]: one end node for an edge
int graph_to[]: the other end node for an edge
int graph_weight[]: the weights of the edges
int source: the source node
int destination: the destination node

Returns

int: the value of the least stressful path. If no path exists, return -1.

Note: Even though edge endpoints are called graph_from[] and graph_to[], this is an undirected graph.

Input Format for Custom Testing

The first line contains two space-separated integers graph_nodes and m, the number of nodes, and the number of edges of the graph. Each of the following m lines contains three space-separated integers a, b, and w meaning there is an edge connecting the nodes a and b of weight w. The next line contains a single integer, denoting the index of the "source" node. The next line contains a single integer, denoting the index of the "destination" node.

𑁍ࠬܓ Credit to Rachel and spike!!⋆｡˚⋆❀ 🐚🫧𓇼 ˖°

Example 1:

Input:  graph_nodes = 4, graph_from = [2, 2, 1, 4], graph_to = [1, 3, 4, 3], graph_weight = [100, 200, 10, 20], source = 1, destination = 3
Output: 20 
Explanation:
      
      
      There are two paths, from node 1 to node 3.
      
      
        The max weighted edge/stress level in path 1 -> 2 -> 3 is 200.
        The max weighted edge/stress level in the path 1 -> 4 -> 3 is 20.
      
      
      Return 20, the lower stress level from the second path.

Constraints:

1 ≤ graph_nodes ≤ 10⁵5

1 ≤ |graph_from| = |graph_to| = |graph_weight| <= 10⁵

1 <= graph_from[i], graph_to[i], source, destination <= graph_nodes

0 <= graph_weight[i] <= 10⁹