a bit of uva: UVa 104 - Arbitrage

Problem Statement:
UVa 104 - Arbitrage

Summary:
Given an adjacency matrix, find the shortest cycle such that the product of the edges is bigger than 1.01

I was stuck on this problem for a while (I sincerely think that this question is difficult! haha) because a lot of people said they solved this problem simply by running Floyd-Warshall on the graph. However, I really don't think that the implementation is that obvious. Eventually, I learnt a way to solve the problem, it resembles Floyd-Warshall, but not exactly the same. It borrows the main idea that we can incrementally build an optimal path by considering k = 1,2,...,N one by one.

The idea is this:
Suppose we are given a path with $m$ edges for each pair of vertices $(i,j)$such that the product of the edges is maximum (in other words, the optimal path using $m$ edges). Then to find the optimal path between $i,j$ using $m+1$ edges can be done by trying all $k = 1,2,3,\ldots, N$ and choose $k$ such that the path i-k-j (where i-k has $m$ edges, k-j is a direct edge\) is optimal. That means, we take D[i][j][m+1] = max of ( D[i][k][m] * D[k][j][1] ) for k = 1,2,...,N. Now it remains to prove that the path we found is indeed optimal, and the proof is by contradiction. Suppose that there is $p$ = i-k'-j (where i-k' has m edges, k'-j is a direct edge) with $k' \neq k$ such that the product of its edges are larger than that of i-k-j. Furthermore, suppose that $q$ is the path i-k'-j such that i-k' is the optimal path using m edges. Then we have: product of edges of $p$ $\leq$ product of edges of $q$ < product of edges of i-k-j, contradiction. Therefore i-k-j found must have been optimal.

As such we can solve the problem by iterating through m starting from m = 2, with the initial condition of m=1 which is the initial adjacency matrix. We also need to maintain a path matrix to reconstruct the path found. This is done by storing the information about the parent of j in a path between i and j: At first, every parent of j is i for all i-j. During the progress of the algorithm, if i-k-j is larger than i-j, update par[i][j] = k (since the parent of j is now k).

Implementation:

void floyd(){
   for(int s=1;s<N;++s) //0 indexed
      for(int k=0;k<N;++k)
         for(int i=0;i<N;++i)
            for(int j=0;j<N;++j){
               double temp = arb[i][k][s-1]*arb[k][j][0];
               if(temp > arb[i][j][s]){
                  arb[i][j][s] = temp;
                  par[i][j][s] = k; //since par[k][j][0] = k
               }
            }
}