uva104 (DP + floyd)

제목 대의: 두 나라 간의 환율을 주고 어느 나라에서 출발하든지 1(단위 불명)을 가지고 이 나라로 돌아갈 때 가진 돈은 > 1.01.그리고 이런 경로가 여러 가지가 있다면 가장 짧은 경로를 원하고 가장 짧은 경로를 출력해 달라고 요구한다.
사고방식:DP를 이용하여 i에서 j까지 l개국을 거쳐 얻은 돈을 구한다.그러면 dp[i][j][1]은 i에서 j 국가 간의 환율을 나타내기 때문에 dp[i][j][l]=max(dp[i][j][l], dp[i][k][l-1]*dp[k][j]]를 나타낸다.만약에 한 나라에서 이 나라로 돌아가는 돈을 만족시키는 > 1.01이 나타나면 순환에서 물러난다. 그러면 도경을 보장할 수 있는 국가가 가장 적고 가장 짧은 경로를 찾을 수 있기 때문이다.코드:

#include <iostream>
using namespace std;
#include <stdio.h>
#include <cstring>

const int N =25;
double dp[N][N][N],p[N][N][N];
int n;
void print(int i,int j,int l) {
    if(l == 0){
        printf("%d",i);
        return;
    }
    print(i,p[i][j][l],l - 1);
    printf(" %d",j);
    return;
}
void DP() {

    int l;
    int m;
    for(l = 2; l <= n; l++) {
        for(int i = 1; i <= n; i++) 
            for(int j = 1; j <= n; j++) 
                for(int k = 1; k <= n; k++) 
                    if(dp[i][j][l] < dp[i][k][l - 1] *dp[k][j][1]) {
                        dp[i][j][l] = dp[i][k][l - 1]*dp[k][j][1];
                        p[i][j][l] = k;
                    }
        int i;
        for(i = 1; i <= n; i++)
            if(dp[i][i][l] > 1.01) {
                m = i;
                break;
            }
        if(i <= n) 
            break;
    }
    if(l > n)
        printf("no arbitrage sequence exists");
    else
        print(m,m,l);
    printf("
");
}
int main() {
    while(scanf("%d",&n) != EOF) {
        memset(dp,0,sizeof(dp));
        memset(p,-1,sizeof(p));
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++) {
                if(i == j)
                    dp[i][j][1] = 1;
                else
                    scanf("%lf",&dp[i][j][1]);
                p[i][j][1] = j;
            }
        DP();
    }
    return 0;
}