uvaoj 208 내 프로그램 속도를 향상시킬 수 있습니까

Question

왜 내 프로그램 시간 제한 오류? 정렬 때문에 ? 이 당신은 끝을지나 tails 및 map을 액세스하는 질문 시작에 대한 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; 
} 

Answer 1

정렬 알고리즘이 최악의 경우 O (n * n)이므로 InnoSort를 사용하면 더 좋은 최악의 경우의 복잡도 O(n*log(n))을 사용할 수 있습니다.

C++을 사용하는 경우 가장 간단한 작업을 수행하려면 <algorithm> 헤더의 sort 함수를 사용하십시오.

문서는 다음에서 찾을 수 있습니다. http://www.sgi.com/tech/stl/sort.html

Answer 2

입니다. C++ 배열은 인덱스가 0이므로 첫 번째 요소는 0이고 마지막 유효한 요소는 tails[21] 및 map[21][43]입니다.