MovingPath

Graph problems are a fairly well known area of computer science. A graph is a set of nodes, and edges that connect one node to another. For example, the following ASCII art represents a simple graph with 4 nodes and 3 edges ('x's represent nodes):

     x
     |
     |
 x---x---x

A common graph problem is to find the shortest path from one node, u, to another node, v, in a graph whose edges have weights. A path in a graph from u to v is a sequence of edges. The first edge in the sequence starts at u, and the last edge in the sequence ends at v. For all pairs of edges that are adjacent in the sequence, the ending node of the earlier edge is the same as the starting node of the later edge. A shortest path from u to v in a weighted graph is a path from u to v, the sum of whose edge weights is minimized.

In this problem, we will be dealing with a randomly generated graph, whose edge weights mutate over time. You will be given six ints as input: nodes, u, v, A, B, and M. You are to use the following algorithm to generate a fully connected graph (one where there is an edge from every node to every other node):

    cur = 1
    for i = 0 to nodes - 1
        for j = 0 to nodes - 1
           if(i does not equal j)
               cur = ((cur * A) + B) % M
               weight(i,j) = (cur % 1000) + 1
           else
               weight(i,j) = 1
           end if
        end for
    end for

This will give you the initial weights on the graph. Whenever an edge is followed, the following algorithm is applied a number of times equal to the weight on the edge, immediately after it is followed (note that the cur here is the same cur as above, and that we never reset its value):

    for i = 0 to nodes - 1
        for j = 0 to nodes - 1
            if(i does not equal j)
                cur = ((cur * A) + B) % M
                weight(i,j) = weight(i,j) + (cur % 21) - 10
                if(weight(i,j) < 1) 
                    weight(i,j) = 1
                end if
            end if
        end for
    end for

Note that, in addition to the random edges generated by this algorithm, there is also an edge from every node to itself of weight 1 that never mutates.

The simplest way to think about this is that the weight on an edge represents the amount of time it takes to traverse that edge, and while the edge is being traversed, the weights on all of the edges between different nodes mutate once for each time unit. However, the amount of time that it takes to traverse an edge is locked in as soon as we start to traverse it. For example, lets say we wanted to traverse an edge of weight 3. It would take 3 time units to traverse the edge, and so we would apply the mutation algorithm given above 3 times. Even though the weight of the edge being traversed may be changed by this process, we use the weight of the edge at the moment that we began to traverse it.

Your task is to generate the graph using the random algorithm given, and then return the length of the shortest path through the graph from node u to node v.