This is the easy version of the problem. The difference between the versions is that in…
- User
This is the easy version of the problem. The difference between the versions is that in this version, there is an additional constraint on m . You can hack only if you solved all versions of this problem.
Recently, the instructors of "T-generation" needed to create a training contest. They were missing one problem, and there was not a single problem on graphs in the contest, so they came up with the following problem.
You are given a connected weighted undirected graph with n vertices and m edges, which does not contain self-loops or multiple edges.
There are q queries of the form (a,b,k) : among all paths from vertex a to vertex b , find the smallest k -th maximum weight of edges on the path† .
The instructors thought that the problem sounded very interesting, but there is one catch. They do not know how to solve it. Help them and solve the problem, as there are only a few hours left until the contest starts.
† Let w1≥w2≥…≥wh be the weights of all edges in a path, in non-increasing order. The k -th maximum weight of the edges on this path is wk .
Input Each test contains multiple test cases. The first line contains a single integer t (1≤t≤100 ) — the number of test cases. The description of the test cases follows.
The first line of each set of test case contains three integers n,m and q (2≤n≤400 , n−1≤m≤min(400,n⋅(n−1)2) , 1≤q≤3⋅105 ) — the number of vertices, the number of edges, and the number of questions, respectively.
Each of the following m lines of each set of test case contains three integers v,u and w (1≤v,u≤n , 1≤w≤109 ) — the ends of the next edge of the graph and its weight, respectively. It is guaranteed that the graph does not contain self-loops and multiple edges.
Each of the following q lines of each set of test case contains three integers a,b and k (1≤a,b≤n , k≥1 ) — the next question. It is guaranteed that any path from vertex a to vertex b contains at least k edges.
It is guaranteed that the sum of the values of n across all sets of test cases does not exceed 400 .
It is guaranteed that the sum of the values of m across all sets of test cases does not exceed 400 .
It is guaranteed that the sum of the values of q across all sets of test cases does not exceed 3⋅105 .
Output For each test case, output the answers to all questions.
Example InputCopy 3 4 4 2 1 2 2 2 4 2 1 3 4 3 4 1 1 4 2 2 3 1 6 7 3 1 2 10 2 3 3 3 4 9 4 5 2 5 6 1 2 4 10 4 6 10 1 6 3 1 6 2 2 4 1 11 17 10 1 4 5 1 3 19 1 2 10 3 2 13 4 5 1 4 6 11 3 5 9 3 6 18 2 7 17 5 8 15 5 10 8 6 9 4 7 10 20 7 8 16 8 11 3 9 11 6 10 11 14 3 11 1 3 11 3 1 11 1 1 11 4 1 11 3 8 2 2 10 4 1 3 9 2 3 9 1 6 7 3 OutputCopy 1 2 2 9 9 11 3 11 1 3 10 8 4 11 4 Note In the first set of test cases, one of the optimal paths in the first query is the path 1→3→4 ; the 2 -nd maximum weight of the edges on this path is 1 . In the second query, one of the optimal paths is 2→4→3 ; 1 -st maximum weight of the edges is 2 .
In the second set of input data, one of the optimal paths in the first query is the path 1→2→4→5→6 ; the 3 -rd maximum weight of the edges on this path is 2 .TYPE WITH MY HINTS:Hint 1: Utilize Binary Search to Determine the Optimal Edge Weight To efficiently find the smallest k-th maximum edge weight on a path from vertex a to vertex b, consider employing a binary search approach on the range of possible edge weights.
Define the Search Space: Identify the minimum and maximum edge weights in the graph to establish the boundaries for binary search. Perform Binary Search: For each mid-value in the binary search, determine if there exists a path from a to b where the k-th maximum edge weight is less than or equal to this mid-value. Adjust the search space based on whether such a path exists, narrowing down to the smallest feasible k-th maximum weight. This method allows you to efficiently converge on the minimal k-th maximum edge weight by systematically eliminating infeasible weight thresholds.Hint 2: Implement a Modified BFS or DFS to Validate Path Constraints After setting up the binary search, you need a way to verify if a valid path exists under the current weight constraint. Modify traditional graph traversal algorithms to accommodate the k-th maximum edge condition.
Track Edge Weights: During traversal, keep track of the largest k edge weights encountered on the current path. Validate Path Feasibility: Ensure that the k-th maximum edge weight does not exceed the current mid-value from the binary search. If such a path exists, it means the current mid-value is a potential candidate for the minimal k-th maximum. By integrating this tracking mechanism into BFS or DFS, you can effectively determine the existence of valid paths that meet the k-th maximum edge weight criteria, thereby supporting the binary search strategy.!
- Assistant
To solve this problem efficiently, given the constraints, we can employ a dynamic programming (DP) approach. Here's a detailed explanation of the solution followed by the implementation in C++.
Solution Overview
Given a connected undirected graph with
nvertices andmedges, and multiple queries asking for the minimal possible k-th maximum edge weight on any path from vertexato vertexb, we need to preprocess the graph to answer these queries efficiently.Key Observations:
-
Dynamic Programming Approach:
- We can define a DP table
dp[a][b][k]wheredp[a][b][k]represents the minimal possible k-th maximum edge weight on any path fromatob. - We initialize
dp[a][a][0] = 0since the path from a vertex to itself with 0 edges has a k-th maximum edge weight of 0. - For each vertex
a, we perform a series of transitions forkfrom1ton-1to update the DP table based on the edges.
- We can define a DP table
-
Transition:
- For each
k, and for each edge(u, v, w), we update the DP table as: [ dp[a][v][k] = \min(dp[a][v][k], \max(dp[a][u][k-1], w)) ] - This transition ensures that for each path to vertex
vwithkedges, we keep track of the minimal k-th maximum edge weight.
- For each
-
Complexity Considerations:
- The time complexity per test case is ( O(n \times m \times k) ), which is manageable given the constraints:
- Sum of
nacross all test cases ≤ 400 - Sum of
macross all test cases ≤ 400
- Sum of
- Memory usage is also manageable since we store a 2D DP table per vertex.
- The time complexity per test case is ( O(n \times m \times k) ), which is manageable given the constraints:
Implementation Steps:
-
Input Parsing:
- Read the number of test cases
t. - For each test case:
- Read
n,m, andq. - Read the
medges and build an adjacency list. - Read the
qqueries.
- Read
- Read the number of test cases
-
Dynamic Programming:
- For each vertex
afrom1ton:- Initialize a
dp_prevarray to keep track of the minimal k-th maximum edge weights for the previousk-1. - Iterate
kfrom1ton-1:- For each vertex
u, update thedp_currentbased on the edges fromu. - Update
dp_prevfor the next iteration. - Store the computed values in a separate DP table
results.
- For each vertex
- Initialize a
- For each vertex
-
Answering Queries:
- After preprocessing, for each query
(a, b, k), simply outputresults[a][b][k].
- After preprocessing, for each query
Optimizations:
-
Memory Optimization:
- Instead of storing a 3D DP table, we store only two 2D arrays (
dp_prevanddp_current) for each vertexato save memory and improve cache performance.
- Instead of storing a 3D DP table, we store only two 2D arrays (
-
Edge Sorting:
- Although not strictly necessary, sorting edges can sometimes help in pruning unnecessary computations. However, in this specific DP approach, we don't require sorting.
-
Efficient Data Structures:
- Use efficient data structures like vectors and avoid using high-overhead structures like maps or sets within the inner loops.
C++ Implementation
Below is the C++ implementation based on the above approach. The code is optimized for speed and memory usage to handle the given constraints efficiently.
#include <bits/stdc++.h> using namespace std; typedef long long ll; // Fast IO struct FastIO { FastIO() { ios::sync_with_stdio(false); cin.tie(0); } }; int main(){ FastIO fio; int t; cin >> t; while(t--){ int n, m, q; cin >> n >> m >> q; // Build adjacency list vector<vector<pair<int, int>>> adj(n+1, vector<pair<int, int>>()); for(int i=0; i<m; i++){ int u, v, w; cin >> u >> v >> w; adj[u].emplace_back(v, w); adj[v].emplace_back(u, w); } // Initialize results: results[a][b][k] // To save memory, for each test case, store a separate 2D vector // results[a][b][k] where k ranges from 1 to n-1 // Due to memory constraints, we'll handle k separately // So, for each a, we store a vector of n+1 vectors for k // To make it manageable, we'll use a 2D vector for each a and b, with k stored as the index // But it's optimized by processing k sequentially // Initialize a 2D vector for each a, b to store minimal k-th maximum // Initialize results as a vector of vectors of vectors // However, due to memory constraints, use n+1 x n+1 x (n) per test case // Which is feasible as n<=400 and sum n across test cases <=400 // Initialize results[a][b][k] to INF // To save space, use a 2D array for each k // So results[k][a][b] // But implement differently to access per a // Implement as a vector for each a, containing a vector for b, containing k-th max vector<vector<vector<int>>> results(n+1, vector<vector<int>> (n+1, vector<int>(n, INT32_MAX))); // For each a from 1 to n for(int a=1; a<=n; a++){ // Initialize dp_prev: minimal k-th max edge weight to reach each node with k edges // For k=0, only a can be reached with 0, set to 0 // For k>=1, initialize to INF // To optimize, use two 1D arrays: dp_prev and dp_current vector<int> dp_prev(n+1, INT32_MAX); dp_prev[a] = 0; // Iterate k from 1 to n-1 for(int k=1; k<n; k++){ vector<int> dp_current(n+1, INT32_MAX); // For each node u for(int u=1; u<=n; u++){ if(dp_prev[u] < INT32_MAX){ // For each edge from u for(auto &[v, w] : adj[u]){ int new_val = max(dp_prev[u], w); if(new_val < dp_current[v]){ dp_current[v] = new_val; } } } } // Update results[a][b][k] for(int b_node=1; b_node<=n; b_node++){ if(dp_current[b_node] < results[a][b_node][k]){ results[a][b_node][k] = dp_current[b_node]; } } // Prepare for next k dp_prev = dp_current; } } // Read all queries // To answer them efficiently, store them first // as pairs of (a, b, k) and then retrieve from results vector<tuple<int, int, int>> queries(q); for(int i=0; i<q; i++) cin >> get<0>(queries[i]) >> get<1>(queries[i]) >> get<2>(queries[i]); // Answer the queries string output = ""; for(int i=0; i<q; i++){ int a = get<0>(queries[i]); int b = get<1>(queries[i]); int k = get<2>(queries[i]); // Since k starts from 1 to n-1 // And results[a][b][k] is already computed // There's a guarantee that any path from a to b has at least k edges // So results[a][b][k] should have been updated output += to_string(results[a][b][k]) + " "; } // Remove the last space and print if(q >0 ){ output.pop_back(); } cout << output << "\n"; } }Explanation of the Code
-
Fast I/O:
- We disable the synchronization between C and C++ standard streams and untie
cinfromcoutto speed up the input and output operations.
- We disable the synchronization between C and C++ standard streams and untie
-
Adjacency List:
- For each test case, we build an adjacency list
adjwhereadj[u]contains pairs(v, w)representing an edge fromutovwith weightw.
- For each test case, we build an adjacency list
-
Dynamic Programming Table (
results):- We initialize a 3D DP table
resultswhereresults[a][b][k]will store the minimal k-th maximum edge weight on any path fromatob. - We iterate over each vertex
aand perform the DP transitions forkfrom1ton-1. - For each
k, we update theresultstable based on the edge weights and previous DP state.
- We initialize a 3D DP table
-
Processing Queries:
- After preprocessing, we read all the queries and answer them by simply retrieving the precomputed values from the
resultstable.
- After preprocessing, we read all the queries and answer them by simply retrieving the precomputed values from the
-
Optimizations:
- Memory: Although the DP table is 3D, given the constraints, it's feasible. However, in practice, for larger constraints, further optimizations or compression techniques might be required.
- Loop Ordering: The nested loops are ordered to maximize cache locality and minimize runtime.
- String Concatenation: We build the output string first and then print it at once to reduce the number of I/O operations.
Conclusion
This DP-based solution efficiently preprocesses the graph to answer a large number of queries by computing the minimal k-th maximum edge weights for all possible vertex pairs and values of
k. Given the constraints, this approach is both feasible and efficient, ensuring that we can handle up to3 * 10^5queries within the time limits. -