uva 104 - Arbitrage(最短路Floyd)

题目大意：现在有n种货币，给出n行数据，表示该种货币与其他n - 1种货币的汇率，现在想要在这些货币中找到一种一种货币，经过交换最少的次数使得金额的数量增加（汇率大于1.01），输出方案。

解题思路：没什么思路，看了别人的题解上说用一个三维数组g[i][j][p]表示有第i种货币经过p次交换后变成第j种货币的最大汇率， 然后就试着去做了一下， 对于每一个p处理后考虑g[i][i][p]的汇率是否大于1.01。处理过程中就是类似与Floyd算法中的那样，对每组i,j, k进行判断。

#include   
#include   
const int N = 30;  
int n, d[N][N][N];  
double g[N][N][N];  
  
void init() {  
    memset(g, 0, sizeof(g));  
    for (int i = 0; i < n; i++) {  
        for (int j = 0; j < n; j++) {  
            if (i != j) {  
                scanf("%lf", &g[i][j][1]);  
                d[i][j][1] = i;  
            }  
        }  
    }  
}  
  
void print(int x, int y, int p) {  
    if (p == 0)  
        printf("%d", x + 1);  
    else {  
        print(x, d[x][y][p], p - 1);  
        printf(" %d", y + 1);  
    }  
}  
  
void floyd() {  
    for (int p = 1; p < n; p++) {  
        for (int k = 0; k < n; k++) {  
            for (int i = 0; i < n; i++) {  
                for (int j = 0; j < n; j++) {  
                    if (g[i][k][p] * g[k][j][1] >





 g[i][j][p + 1] + 1e-9) {  
                        g[i][j][p + 1] = g[i][k][p] * g[k][j][1];  
                        d[i][j][p + 1] = k;  
                    }  
                }  
            }  
        }  
  
        for (int i = 0; i < n; i++) {  
            if (g[i][i][p + 1] > 1.01) {  
                print(i, i, p + 1);  
                printf("\n");  
                return ;  
            }  
        }  
    }     
    printf("no arbitrage sequence exists\n");  
}  
  
int main () {  
    while (scanf("%d", &n) == 1) {  
        init();  
        floyd();  
    }  
    return 0;  
}