UVa 10496

classic TSP problem again, the same with UVa 216

/* UVas */
/*****************************************************************************/
int t, r, c, n;
int xs, ys;
int main(void) {
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d", &r, &c);
        scanf("%d %d", &xs, &ys);
        scanf("%d", &n);
        n++;
        int x[n], y[n];
        int g[n][n];
        int d[n][1<<n];
        int p[n][1<<n];
        x[0]=xs, y[0]=ys;
        for (int i=1; 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]=abs(x[i]-x[j])+abs(y[i]-y[j]);
        for (int i=0; i<n; i++) {
            fill(d[i], d[i]+(1<<n), INT_MAX);
            d[i][(1<<n)-1]=0;
        }
        memset(p, 0, sizeof(p));
        for (int mask=(1<<n)-2; 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]) {
                                d[i][mask]=d[j][mask|(1<<j)]+g[i][j];
                                p[i][mask]=j;
                            }
        int s=0;
        int mask=1;
        while (mask!=(1<<n)-1) {
            int j=p[s][mask];
            mask|=(1<<j);
            s=j;
        }
        printf("The shortest path has length %d\n", d[0][1]+g[0][s]);
    }
}
/*****************************************************************************/