Página Principal

MC521-1s2014

MC621-2s2014

MC521-1s2015

MC621-2s2015

MC521-1s2016

Conteúdo

Área Reservada

edit sidebar

UVA 590

Autor: Felipe Castro

#include <cstdio>
#include <cstdlib>
#include <cmath>
#define INF 2e9

using namespace std;

int main(){
        int costs[20][20][40];
        int numFlights[20][20];
        int dp[20][1100];
        int n, k, i, j, l, cases = 0, diaAtual;

        while(1){
                cases++;

                scanf("%d %d", &n, &k);

                if(!n && !k)
                        break;

                for(i = 1; i <= n; i++){
                        for(j = 1; j <= n; j++){
                                if(i != j){                    
                                        scanf("%d", &numFlights[i][j]);

                                        for(l = 1; l <= numFlights[i][j]; l++){
                                                scanf("%d", &costs[i][j][l]);
                                        }
                                }
                        }
                }

                for(i = 0; i <= n; i++)
                        for(j = 0; j <= k; j++)
                                dp[i][j] = INF;

                dp[1][0] = 0;

                for(l = 1; l <= k; l++){
                        for(i = 1; i <= n; i++){
                                for(j = 1; j <= n; j++){
                                        if (i != j){
                                                diaAtual = (l - 1) % numFlights[j][i] + 1;

                                                if (costs[j][i][diaAtual] && dp[j][l - 1] != INF)
                                                        dp[i][l] = fmin(dp[i][l], dp[j][l - 1] + costs[j][i][diaAtual]);
                                        }
                                }
                        }
                }                    

                printf("Scenario #%d\n", cases);

                if (dp[n][k] != INF)
                    printf("The best flight costs %d.\n\n", dp[n][k]);
                else
                    printf("No flight possible.\n\n");
        }

        return 0;
}