Voltar

Biroute - Grafos

0 Curtidas

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>

#define MAXP 60
#define SQ(X) ((X)*(X))

using namespace std;

double T[MAXP][MAXP];
bool comp[MAXP][MAXP];
double point[MAXP][2];
int N;

double dist(int p1, int p2) {
    double ans = 0;
    for (int i=0; i<2; i++) {
        ans += SQ(point[p1][i]-point[p2][i]);
    }
    return sqrt(ans);
}
   

double minTour(int e1, int e2) {
    //printf("%d %d\n",e1,e2);   
    if (e1==N-1 || e2==N-1) return dist(e1,e2);
    if (comp[e1][e2]) return T[e1][e2];
   
    int n = max(e1,e2)+1;
    double d1 = minTour(n,e2) + dist(e1,n);
    double d2 = minTour(e1,n) + dist(e2,n);
   
    T[e1][e2] = min(d1,d2); T[e2][e1]=T[e1][e2];
    comp[e1][e2] = true; comp[e2][e1]=true;
    //printf("%d %d: %lf\n",e1,e2,T[e1][e2]);
    return T[e1][e2];
}

int main() {
    while ( scanf("%d",&N) != EOF ) {
        for (int i=0; i<N; i++) {
            scanf("%lf %lf", &point[i][0], &point[i][1]);
        }
        for (int i=0; i<=N; i++)
            for (int j=0; j<=N; j++)
                comp[i][j]=false;
        double ans = minTour(0,0);
        printf("%.2lf\n",ans);
    }
}

Problemas relacionados
  Nome Comentário
Ainda não há nenhum problema relacionado a esse conteúdo

Comentários


Postagens neste fórum só são permitidas para membros com conta ativa. Por favor, efetue login or cadastro para postar.