Hello, codeforces! Could someone try to pass my solution in 299702131? The idea is to iterate over n, then k, then run Dial's algorithm (for widest path) over the graph, then skip an edge to make the initial distances for k+1.
I'm reasonably sure the approach is O(n^2m) (confirmed by a friend). The code runs in 600ms on a random case on my laptop. Can someone constant optimize it for me, or tell me why it doesn't pass? Thanks!
I dealt with the same problem in contest. The main problem is not time complexity its memory complexity. It TLE's because it is taking too much time to process all the memory (this is what I think). My code also had a N^3 array for distances but I optimized it to only have one N^2 which made it pass.
299814561 still doesn't pass D:
Ok, I found the problem now. It works in C++17, that's for sure. It works in less than 1300 ms. I have no idea why it doesn't work in C++23 tho... This is ac sumission: 299826028