PLEASE CODE THIS PROBLEM IN ANY LANGUAGE:

I suggest that you use Dijkstra's algorithm for this problem. You'll have to make a slight change to the algorithm, however, because of the way that factors accumulate.

There is an aspect of this problem that you might not expect. It is possible for there to be multiple corridors with the same endpoints. While this shouldn't cause any problem for Dijkstra's algorithm, be sure that you allow for this in your graph representation.

Some languages, for example Java and C++, provide priority queue implementations. Unfortunately, these implementations may not be exactly what you need. For example, the Java version does not provide an update operation, and the C++ version provides a linear-time update operation which isn't fast enough. Be careful you know what you are getting into when you use libraries.

Nevertheless, it is possible to use both the Java and C++ priority queues. When you need to change the weight of an element that is already in the queue, simply re-insert it with the new weight. The queue will then contain multiple versions of the same element. You just need to be sure to ignore the element when it comes off the queue for the second (or third, or ...) time.

Get Shorty Nils and Mikael are intergalaxial fighters as well as lethal enemies. Now Nils has managed to capture the poor Mikael in his dark dungeons, and it is up to you to help Mikael escape with as much of his pride intact as possible. The dungeons can be viewed as a set of corridors and intersections. Each corridor joins two intersections. There are no guards, traps, or locked doors in Nils' dungeon. However, there is one obstacle which makes escaping from the dungeon a perilious project: in each corridor there is a sentry, armed with a factor weapon. (As is commonly known, a factor weapon with factor f reduces the size of its target to a factor f of its original size, e.g. if Mikael is 8 gobs large and is hit by a factor weapon with factor f= 0.25 his size will be reduced to 2 gobs.) Mikael will not be able to pass through a corridor without being hit by the factor weapon (but luckily enough, reloading the factor weapon takes enough time that the sentry will only have time to shoot him once as he passes through). It seems inevitable that Mikael will come out of this adventure a smaller man, but since the sentries have different factors in their factor weapons, his final size depends very much on the route he takes to the exit of the dungeons. Naturally, he would like to lose as little size as possible, and has asked you to help him accomplish that. Input Input consists of a series of test cases (at most 20). Each test case begins with a line consisting of two integers n, m separated by a single space, where 2 <>