UVa 216

classic TSP problem, the maximum point number is 8, so it can be solved by dynamic programming efficiently, there is also a requirement to record the path with minimum cost, hence...classic solution to the classic problem...
state:
    dp[i][j] - minimum cost when point i is visited, with j points visited
    j is a bitmask indicating how many points we have visited, so the initial state should be
    dp[k][111...111], for all point k, which means we have visited all the points and end at k
    the next NODES in DAG of initial state should be dp[k][111...111&(~(1<<l))], for all points k,
    which means we now end at k, but there is still another point being not visited
transition:
    dp[i][j]=min(dp[i][j], dp[k][j|k]+dist[i][k]+SOME_CONST_COST
    for all k that are not visited

/* UVas */
/*****************************************************************************/
const int N=8;
const double O=16.0;
int n, t=1;
int x[N], y[N];
int p[N][1<<N];
double g[N][N];
double d[N][1<<N];
int main(void) {
    while (scanf("%d", &n)>0&&n) {
        for (int i=0; i<n; i++)
            scanf("%d %d", &x[i], &y[i]);
        for (int i=0; i<n; i++)
            for (int j=0; j<n; j++)
                g[i][j]=hypot(x[i]-x[j], y[i]-y[j]);
        for (int i=0; i<n; i++) {
            fill(d[i], d[i]+(1<<n), (double)INT_MAX);
            fill(p[i], p[i]+(1<<n), 0);
        }
        for (int i=0; i<n; i++)
            d[i][(1<<n)-1]=0.0;
        for (int mask=(1<<n)-1; mask>=0; mask--)
            for (int i=0; i<n; i++) 
                if (mask&(1<<i))
                    for (int j=0; j<n; j++)
                        if (!(mask&(1<<j)))
                            if (d[i][mask]>d[j][mask|(1<<j)]+g[i][j]+O) {
                                d[i][mask]=d[j][mask|(1<<j)]+g[i][j]+O;
                                p[i][mask]=j;
                            }
        int s=0;
        for (int i=1; i<n; i++)
            if (d[i][1<<i]<d[s][1<<s])
                s=i;
        printf("**********************************************************\n");
        printf("Network #%d\n", t++);
        int mask=1<<s;
        int e=s;
        while (mask!=(1<<n)-1) {
            int j=p[s][mask];
            printf("Cable requirement to connect ");
            printf("(%d,%d) to (%d,%d) is %.2lf feet.\n", x[s], y[s], x[j], y[j], g[s][j]+O);
            mask|=(1<<j);
            s=j;
        }
        printf("Number of feet of cable required is %.2lf.\n", d[e][1<<e]);
    }
}
/*****************************************************************************/