Approach with Magical Bridges

[omerjerk]

Hi,

I'm trying to solve spoj.com/problems/AMR11F/.
My first approach was to use dikjstra and represent every floor as a node. But the problem with that is number of floors come out to be 10^8 and that'll go out of memory for sure.

I'm still baffled on how to approach the problem with less number of nodes.

Can anyone please shed some light on this matter ?

Thanks,
Umair

[leppyr64]

This is pretty much the only hint that I can give you for this problem. It also applies to almost every other problem.

Focus on the constraints that are small.

[omerjerk]

This is pretty much the only hint that I can give you for this problem. It also applies to almost every other problem.

Focus on the constraints that are small.

I know that I only need to add those floors to the graph which have bridges connected to them.

But the tough part is for the query.
What if there is no node in my graph for some floor of query ?

[leppyr64]

But the tough part is for the query.
What if there is no node in my graph for some floor of query ?

That is a good question. That is the reason that the only hint that I can give you is the one I gave. If I answer this question then you would not be solving the problem, I would be.