ACM 题目求最优解小弟我TLE了啊

ACM 题目求最优解我TLE了求助啊.
描述：
在二维坐标上给你M个点(M是偶数)的坐标,坐标都是整数,你可以任意联接其中两点(不管中间有没有障碍),这两点就消失了(和游戏里的一样).但消去两点的路径和两个点的位置有关,也就是说路径的长度等于两点X轴与Y轴差的绝对值之和.比如一个点坐标为(10,10),另外一个点坐标为(2,3),那么消去这两个点的路径长度为8+7=15.问消去所有点的路径长度之和最小值是多少?

第一行输一个正整数N,下面有N种连连看的地图

每种地图的第一行输入一个正整数M
(M是偶数,并且2=< M <=20),代表地图上有M个点.
下面有M行,每一行都有两个整数,代表这个点的X轴坐标与Y轴坐标.
(坐标的绝对值不会大于十万)

输出共N行,每行都是消去所有点的路径长度之和的最小值.

Sample Input
3

2
10 10
2 3

2
0 1
0 2

4
0 2
0 3
0 5
0 6

Sample Output
15
1
2

-------------------------
我的方法：

C/C++ code


 #include <stdio.h> 
struct Point  
{  
    int x, y;  
}PointList[21]; 
int g_nSatusList[1024][1024]; 
int g_nPointList[21][21];  
int g_nFlagList[21] = {0};  
int n = 0;  
int valuex = 1023, valuey = 1023;
int max1 = 0, max2 = 0; 
int abs(int argA, int argB)  
{  
    return argA > argB ? argA - argB : argB - argA;  
}
int DeepInto(int Limit)  
{  
    int i = 0 ,j = 0;  
    if (Limit == 2)  
    {  
        int x = -1, y = -1;  
        for (i = 0; i < n; i++)  
        {  
            if (g_nFlagList[i] == 0)  
            {  
                if (x == -1) 
                    x = i; 
                else 
                    y = i; 
            }   
        }  
        return g_nPointList[x][y] == 0 ? g_nPointList[y][x] : g_nPointList[x][y];  
    }
    int minitemp = 200000000;
    int tpj = -1;
    for (i = 0; i < n; i++)  
    {  
        if (g_nFlagList[i] == 0)  
        {  
            if (tpj == -1)
                tpj = i; //记录开始点
            g_nFlagList[i] = 1; 
             
            if (i < 10) 
                valuex = (valuex ^ (1 << i)); 
            else 
                valuey = (valuey ^ (1 << (i - 10))); 

            int j = 0;
            for (j = tpj; j < n; j++)  
            {  
                if (g_nFlagList[j] == 0 && minitemp > g_nPointList[i][j])  
                {  
                    g_nFlagList[j] = 1;  
                     
                    if (j < 10) 
                        valuex = (valuex ^ (1 << j)); 
                    else 
                        valuey = (valuey ^ (1 << (j - 10))); 

                    int temp; 

                    if (g_nSatusList[valuex][valuey] != -1) 
                    { 
                        temp = g_nSatusList[valuex][valuey]; 
                    } 
                    else 
                    {
                        temp = DeepInto(Limit - 2); 
                    }
                    int ijLength = g_nPointList[i][j] == 0 ? g_nPointList[j][i] : g_nPointList[i][j];
                    if (minitemp > ijLength + temp)  
                    {  
                        minitemp = ijLength + temp;  
                    } 

                    if (g_nSatusList[valuex][valuey] == -1 || 
                        g_nSatusList[valuex][valuey] > minitemp) 
                        g_nSatusList[valuex][valuey] = minitemp; 
                    g_nFlagList[j] = 0;  

                    if (j < 10) 
                        valuex = (valuex ^ (1 << j)); 
                    else 
                        valuey = (valuey ^ (1 << (j - 10))); 
                }  
            }  
            g_nFlagList[i] = 0;  
            if (i < 10) 
                valuex = (valuex ^ (1 << i)); 
            else 
                valuey = (valuey ^ (1 << (i - 10))); 
        }  
    }  
    return minitemp;  
}  
void initailArray(int MX, int MY) 
{ 
    int i = 0, j = 0; 
    for (;i < MX; i++) 
        for(j = 0; j < MY; j++) 
            g_nSatusList[i][j] = -1; 
} 
int main ()  
{   
    int CaseN = 0;  
    while (1 == scanf("%d", &CaseN))  
    {  
        while (CaseN--)  
        {  
            scanf("%d", &n);  
            int i = n;
            max1 = 0, max2 = 0;
            while (i--)  
            {  
                scanf("%d %d", &PointList[i].x, &PointList[i].y);
                if (i < 10)
                    max1 = max1 | (1 << i);
                else
                    max2 = max2 | (1 << (i - 10));
            }  
            i = n;  
            while (i--)  
            {  
                int j = 0;  
                while (j < i)  
                {  
                    g_nPointList[i][j] = abs(PointList[i].x, PointList[j].x) +  
                        abs(PointList[i].y, PointList[j].y);  
                    j++;  
                }  
            }  
            i = n; 
            initailArray(max1 + 1, max2 + 1); 
            valuex = max1, valuey = max2;
            printf("%d\n", DeepInto(i));  
        }  
    }  
    return 0;  
}

ACM 题目求最优解 小弟我TLE了啊

相关推荐

ACM 题目求最优解小弟我TLE了啊