trcfx9's blog

By trcfx9, history, 3 years ago, In English

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

  • Vote: I like it
  • -11
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't think that's entirely right.

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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!

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Anyone pls help me.