Problem description : https://www.urionlinejudge.com.br/judge/en/problems/view/1476
My code : http://pastebin.com/9X29pLcf
I have been trying to solve this problem for a while. I'm not sure if my idea is correct (LCA with dfs preprocess and segment tree queries), but i think it is. I have found a test case that breaks my program, and i know the reason my program fails in this case, but i don't know how to fix it because i don't have a lot of experience with LCA algorithm.
Explanation : i want to determine the bottleneck edge in the path from vertex A to vertex B. The query in my segment tree returns the smallest weight, but it considers all vertexes that were visited between A and B in the dfs, and some of these vertexes are not included in the path from A to B.
Any help will be much appreciated! Thanks in advance.
Bad test case:
6 5 8
4 1 39
2 4 80
6 1 29
4 5 35
3 1 21
4 2
4 6
5 1
5 4
4 2
3 4
3 4
5 1
Expected output:
80
29
35
35
80
21
21
35
My program output:
39
29
35
35
39
21
21
35
There is a full explanation from Gabriel Dalalio about all the problems from this contest. Solutions
Try to use kruskal it seems more easy.
Ty very much! I didn't know about this editorial. I used MST algorithm in the first step of my code too (Prim instead of Kruskal) but i messed up the solution when i tried to use LCA in the generated MST.