```cpp #include #include #include #include #include class Solution { public: // n: number of nodes, labeled 0..n-1 // edges: list of (u, v, cost) undirected edges // start, end: node labels for the path endpoints // threshold: only edges with cost <= threshold may be used // // Among all valid start->end paths using only edges with cost <= threshold, // return the minimum possible value of the maximum edge cost on the path. // Return -1 if no such path exists (start == end should return 0). int minMaxEdgePath(int n, std::vector>& edges, int start, int end, int threshold) { if (start == end) return 0; std::unordered_map>> adj; for (const auto &edge : edges) { int u = std::get<0>(edge); int v = std::get<1>(edge); int cost = std::get<2>(edge); adj[u].push_back({v,cost}); adj[v].push_back({u,cost}); } // go from start -- end (from there we track 2 things -- max edge -- but also we track the min edge cost) // we can perform Djikstra edge relaxation -- by maintaining a min pq auto cmp = [](const std::tuple &p1, const std::tuple &p2) { if (std::get<0>(p1) != std::get<0>(p2)) { return std::get<0>(p1) > std::get<0>(p2); } else { return std::get<1>(p1) > std::get<1>(p2); } }; std::priority_queue, std::vector>, decltype(cmp)> pq; // element -- (cost_till_now, max_edge, node) --- std::unordered_set vis; int ans = INT_MIN; pq.push({0, INT_MIN, start}); while (!pq.empty()) { auto [cost_till_now, max_edge, node] = pq.top(); pq.pop(); vis.insert(node); // if node --> end if (node == end) { ans = max_edge; break; } for (auto [ne, cost] : adj[node]) { if (!vis.contains(ne) && cost <= threshold) { pq.push({cost_till_now+cost,std::max(max_edge, cost), ne}); } } } return ans == INT_MIN ? -1 : ans; } }; ```

Quick Overview

Find A Threshold-Limited Path With Minimum Required Safety