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

Problem Link: https://lightoj.com/problem/country-roads

Thanks In Advance

# | User | Rating |
---|---|---|

1 | tourist | 3697 |

2 | Benq | 3583 |

3 | Petr | 3522 |

4 | ecnerwala | 3467 |

5 | Radewoosh | 3466 |

6 | maroonrk | 3369 |

7 | Um_nik | 3358 |

8 | jiangly | 3330 |

9 | Miracle03 | 3314 |

10 | scott_wu | 3313 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 213 |

2 | Errichto | 189 |

3 | awoo | 188 |

4 | rng_58 | 187 |

5 | SecondThread | 186 |

6 | Um_nik | 179 |

7 | Ashishgup | 177 |

8 | maroonrk | 172 |

8 | vovuh | 172 |

8 | antontrygubO_o | 172 |

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

Problem Link: https://lightoj.com/problem/country-roads

Thanks In Advance

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/15/2021 18:16:17 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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

I don't think that's entirely right.

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

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.

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 6

we 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.

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!

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

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.

Brother I think You dont understood the question clearly. Not the minimum distance but the minimum maximum road that you can pass through.

Yes, so you can just use djikstra to solve it. What is unclear?

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.

Bro, I just Aced. I know what I am talking about dude.

Anyone pls help me.

Someone already said the solution. What are you still looking for?

`State - dist[v] - smallest maximum road of all possible paths to get to node v`

`Transition - for every outgoing edge pair(next,length) from v, if dist[next] > max(dist[v],length) then relax it`