Hey Everyone,
I'm trying to solve problem 1679D, but I'm getting TLE despite using the strategy suggested by the editorial. The basic idea behind this problem is that you have a graph and each node has a weight. You need to find the path with the minimum-maximum weight, where the path must be at least k vertices. The strategy suggested by the editorial is to:
- Binary search for the optimal weight
- Verify potential weights by creating a graph of only nodes with that weight or less...
- Perform a topological sort on that graph, use that sort to calculate the maximum path, and return true if that maximum path exceeds the minimum vertices k.
Unfortunately, when I implemented this strategy, I got TLE. Any help in understanding this problem would be greatly appreciated!
Code: https://codeforces.me/contest/1679/submission/166858130
