c++ - uvaoj 208我如何加快我的程序

为什么我的程序限时错误？
因为排序？
这是问题
link text

#include <cstdio>
#include <cstring>

using namespace std;

int map[22][44];
int book[22];
int total;
int sum;
int way[22];
int tails[22];
int tail;

void init()
{
 memset(map,0,sizeof(map));
 memset(book,0,sizeof(book));
 sum =0;
 memset(way,0,sizeof(way));
 way[1]=1;
 memset(tails,0,sizeof(tails));
}

void sort()
{
 int t;
 for (int i=1;i<=22;i++)
  {
   if (tails[i]==0)
    break;
   else
    {
     for (int j=1;j<=tails[i]-1;j++)
      for (int k=j+1;k<=tails[i];k++)
       {
        if (map[i][j] > map[i][k])
         {
          t = map[i][j];
          map[i][j]=map[i][k];
          map[i][k]=t;
         }
       }
    }
  }
}

void dfs(int x,int y)
{
 if ((x < 1)||(x > 22))
  return;
 if (book[x]==1)
  return;
 //printf("%d \n",x);
 if (x == total)
  {
   sum++;
   for (int i=1;i<=y-1;i++)
   {
    printf("%d ",way[i]);
   }
   printf("%d",total);
   printf("\n");
   return;
  }
 tail = tails[x];
 for (int i=1;i<=43;i++)
  {
   book[x]=1;
   way[y]=x;
   dfs(map[x][i],y+1);
   book[x]=0;
  }
}

int main()
{
 int temp1,temp2;
 //freopen("ex.in","r",stdin);
 //freopen("ex.out","w",stdout);
 int c = 0;
 while(scanf("%d",&total)!=EOF)
 {
 c++;
 printf("CASE ");
 printf("%d",c);
 printf(":");
 printf("\n");
 init();
 for (;;)
  {
   scanf("%d%d",&temp1,&temp2);
   if ((temp1 == 0)&&(temp2 == 0))
    break;
   else
    {
     tails[temp1]++;
     tail = tails[temp1];
     map[temp1][tail]=temp2;
     tails[temp2]++;
     tail = tails[temp2];
     map[temp2][tail]=temp1;
    }
  }
  sort();
  dfs(1,1);
  printf("There are ");printf("%d",sum);printf(" routes from the firestation to streetcorner ");printf("%d",total);printf(".");
  printf("\n");
 }
 return 0;
}

最佳答案

因为您的排序算法为最坏情况O（n * n），所以您可以使用InnoSort获得更好的最坏情况复杂度O(n*log(n))。

您正在使用C ++，然后使用sort标头中的<algorithm>函数来做到这一点最简单。

您可以在http://www.sgi.com/tech/stl/sort.html上找到的文档

关于c++ - uvaoj 208我如何加快我的程序，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/3178928/