ACM: 104 - Arbitrage

這一題我原先使用了brute force找出所有的換匯途徑，再檢查是否獲利，但這樣會超過time limit，有效率的解法必須使用Floyd-Warshall演算法。參考了Mat所轉錄的文章，研究了一陣，才了解Floyd-Warshall演算法一層層找最佳中繼點，最後再重建路徑回去的方法！但想通了真覺得Floyd-Warshall很美妙呢！

這題可說是找一個weighted graph從一點開始再回到一點的最短路徑，例如(0,.., 0)，先找第一個最佳中繼點(0, k1, 0)，紀錄下這個k1後，再找第二層中繼點(k1, k2, 0)，再紀錄下k2然後繼續…。最後，再從最後kn中繼點，重建回k1，便可以重建(0, k1, k2, .., kn, 0)的完整路徑了。

在我的code裡面，我一找到獲利的路徑後就跳出floyd-warshall。跟這題奮鬥多天的結果是Runtime 0.044，Rank 88！開心！

CODE

#include <stdio.h>

#define MAX 20

double profit[MAX][MAX][MAX];
int n, st, path[MAX][MAX][MAX];

int fw(void);

int main(){
  int i, j, s;
  int final[MAX];
  
  while( scanf("%d", &n) != EOF ){
    /*initialize profit array*/
    for(s=0; s<n; s++){
      for(i=0; i<n; i++){
        for(j=0; j<n; j++){
          profit[s][i][j] = 0.0;
        }/*j*/
      }/*i*/
    }/*s*/
    
    /*read rates table*/
    for(i=0; i<n; i++){
      for(j=0; j<n; j++){
        if( i==j )
          profit[0][i][j] = 1.0;
        else
          scanf("%lf", &profit[0][i][j]);
        path[0][i][j] = i;
      }
    }
    
    /*Floyd-Warshall*/
    if( (s = fw()) > 0 ){
      /*Re-construct path*/
      final[0] = j = st;
      i = s;
      for(i; i>0; i--){
        final[i] = path[i][st][j];
        j = final[i];
      }
      
      for(i=0; i<=s; i++){
        printf("%d ", final[i]+1);
      }
      printf("%d\n", st+1);
    }
    else{
      printf("no arbitrage sequence exists\n");
    }
  }/*while input data*/
  
  exit(0);
}

/*Return step when arbitrage exists; Return 0 when no arbitrage exists*/
int fw(void){
  int i, j, k, p;
  int s;
  double tmp;
  
  for(s=1; s<n; s++){
    for(k=0; k<n; k++){
      for(i=0; i<n; i++){
        for(j=0; j<n; j++){
          tmp = profit[s-1][i][k] * profit[0][k][j];
          if( tmp > profit[s][i][j] ){
            profit[s][i][j] = tmp;
            path[s][i][j] = k;
          }
        }/*j*/
      }/*i*/
    }/*k: intermediate node*/
    
    
    /*check if arbitrage exists*/
    for(p=0; p<n; p++){
      if( profit[s][p][p] > 1.01 ){
        st = p;
        return s;
      }
    }
  }/*s: step*/
  
  return 0;
}