Poj Solution 2677

http://poj.org/problem?id=2677

#include <stdio.h>
#include <memory.h>
#include <math.h>

struct point
{
    double x, y;
};
double dis( point &a, point &b )
{
    return sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) );
}
double s[1010][1010];
point p[1010];
int main( )
{
    int n, i, j;
    double t, ans;
    while( scanf( "%d", &n ) == 1 )
    {
    
        for( i=1; i<=n; i++ )
            scanf( "%lf %lf", &p[i].x, &p[i].y );
        p[0].x = p[1].x;
        p[0].y = p[1].y;
        n++;
        for( i=0; i<n; i++ )
        for( j=i+1; j<n; j++ )
            s[i][j] = -1;
        s[0][1] = 0;
        for( i=0; i<n-1; i++ )
        for( j=i+1; j<n-1; j++ )
        {
            t = s[i][j] + dis( p[i], p[j+1] );
            if( s[j][j+1] == -1 || t < s[j][j+1] )
                s[j][j+1] = t;

            t = s[i][j] + dis( p[j], p[j+1] );
            if( s[i][j+1] == -1 || t < s[i][j+1] )
                s[i][j+1] = t;
        }
        ans = 1e100;
        for( i=0; i<n-1; i++ )
            if( ans > ( t = s[i][n-1] + dis( p[i], p[n-1] ) ) )
                ans = t;
        printf( "%.2lfn", ans );
    }
    return 0;
}