trcfx9's blog

By trcfx9, history, 5 weeks 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

»
5 weeks 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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't think that's entirely right.

    • »
      »
      »
      5 weeks 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

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

»
5 weeks 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!

  • »
    »
    5 weeks 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

»
5 weeks 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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Anyone pls help me.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

    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