### trcfx9's blog

By trcfx9, history, 5 weeks ago,

How to solve this? Tried a lot but didn’t come up an idea.

• -11

 » 5 weeks ago, # |   0 This is a MST (minimum spanning tree) problem. After knowing the mst the minimum biggest road from a to b is just the biggest road in the mst from a to b
•  » » 5 weeks ago, # ^ |   0 I don't think that's entirely right.
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Actually I can prove it.Let R be the minimum maximum road from a to b. Let's say R is not on the mst. That means that R is bigger or equal to all the nodes that ensure connectivity from a to b. But if a and b are connected by roads that are smaller than R it becomes an absurdity. So R is on the MST by contradiction
•  » » » » 5 weeks ago, # ^ |   0 Ok, I know what you are saying. However, building a MST doesn't work for this problem because we don't need to take into account all of the edges and connect them. We can just run djikstra to find the shortest path.
•  » » » » » 5 weeks ago, # ^ |   0 Lets say we have a graph G and we want to determine the shortest path between two nodes on G. We shouldn't use a minimum spanning tree to find the shortest path between these, because there might be some extra nodes on the minimum spanning tree that doesn't involve the graph at all. Let's say our graph is a tree and we want to find the minimum distance between two nodes. Building an MST would give the wrong answer here as there would be extra nodes that we don't need. Consider the following graph (Edge, Edge, Cost) 1 2 1 2 3 4 3 4 6we are asked to find the shortest path from 1 to 3. In your example, we would build an MST and that would contain 1, 4, and 6. However, the answer is 4 because we don't need to include the edge between 3 and 4.
 » 5 weeks ago, # | ← Rev. 2 →   0 Think about this problem in reverse. The shortest path to get from all those cities to city t is the shortest path to get from city t to all the cities, but first, run bfs or dfs from city t and keep a list of the nodes you can visit. Run Dijkstra from node t to all the other cities (Ideal time would be O(E log V) with Fibonacci heap). Then determine if you can visit node i from city t. If you can, output the distance gathered from Djikstra, and if you can't, print Impossible.The total time complexity of this is T*(E log V) or according to google, 2.86 million, which should pass, depending on the language you're using. If you are having any confusion on how to run a Djikstra, I believe there is an implementation in the CSES book.Please DM me if you have any concerns about implementation or if my comment did not make sense, and I will try to answer your questions.Have a nice day!
•  » » 5 weeks ago, # ^ |   0 The thing is, the question is not the minimum distance but the minimum maximum road that you can pass through In this image for example the exercise tells that the optimal path is 0-3-4 even though 0-1-4 is the shortest path. There is actually a way to modify the dijikstra to make it work, but it's the same algorithm to find the MST
 » 5 weeks ago, # |   0 You can keep track of all the places that you can reach using DSU from node t. Then if they're not in the same connected components, you can print "Impossible" because there is no way to reach node u from node t. Then you can run Dijkstra's algorithm from node t which finds the shortest path from node t to all other nodes.
•  » » 5 weeks ago, # ^ |   0 Brother I think You dont understood the question clearly. Not the minimum distance but the minimum maximum road that you can pass through.
•  » » » 5 weeks ago, # ^ |   0 Yes, so you can just use djikstra to solve it. What is unclear?
•  » » » » 5 weeks ago, # ^ |   0 Bro use Dijkstra you just find the minimum wieght from a path but we need the maximum cost road from a path not the whole cost. I think you miss understood the problem statement.
•  » » » » » 5 weeks ago, # ^ |   0 Bro, I just Aced. I know what I am talking about dude.
 » 5 weeks ago, # |   +1 Anyone pls help me.
•  » » 5 weeks ago, # ^ |   0 Someone already said the solution. What are you still looking for?
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 State - dist[v] - smallest maximum road of all possible paths to get to node vTransition - for every outgoing edge pair(next,length) from v, if dist[next] > max(dist[v],length) then relax it