UVa 341. Non-Stop Travel. [판정:TLE]

STLW2로 이사하고나서 처음 올리는 솔루션인 것 같은데

무식하게 탐색해서 그런지 결국 TLE를 먹었군요 -_-;

#include 
using namespace std;

#define MROUTE 30 // maybe most number of routes

// 1st column is departure, 2nd column is destination, 3rd column is delay
// 90 row are most number of streets
int ary[90][3];
int nost = 0; // number of existing streets

// 1st~10th column are passed intersection list, 11th column is total delay, 12th column is length-1
int route[MROUTE][12];
int used_row = 0;

int intersection;

void push( const int depar, int st_nth, int rt_nth, const int depth );
int findroute( const int departure, int destination, int depth );

int main()
{
	int num = 1;
	int min_delay;
	int mdroute;

	scanf( "%d", &intersection );

	while( intersection != 0 )
	{
		int i, j;
		int nodes; // number of destination
		int depar, desti;

		// input data
		for( i = 1; i <= intersection; i++ )
		{
			scanf( "%d", &nodes );

			for( j = 0; (nodes != 0) && (j < nodes); j++, nost++ )
			{
				ary[nost][0] = i;
				scanf( "%d %d", &ary[nost][1], &ary[nost][2] );
			}
		}
		scanf( "%d %d", &depar, &desti );

		// checking
		findroute( depar, desti, 1 );

		// output data
		min_delay = 10000000;
		mdroute = 0;
		for( i = 0; (route[i][0] != 0) && (i < MROUTE); i++ )
		{
			if( min_delay > route[i][10] )
			{
				for( j = 9; j >= 0; j-- )
				{
					if( route[i][j] != 0 )
					{
						break;
					}
				}

				if( route[i][j] == desti )
				{
					min_delay = route[i][10];
					mdroute = i;
				}
			}
		}

		printf( "Case %d: Path =", num );
		for( j = 0; (route[mdroute][j] != 0) && (j < 10); j++ )
		{
			printf( " %d", route[mdroute][j] );
		}
		printf( "; %d second delay\n", min_delay );

		// new map will be check or terminate program
		scanf( "%d", &intersection );

		if( intersection != 0 )
		{
			for( i = 0; i < nost; i++ )
			{
				ary[i][0] = ary[i][1] = ary[i][2] = 0;
			}
			for( i = 0; i < used_row; i++ )
			{
				for( j = 0; j < 12; j++ )
				{
					route[i][j] = 0;
				}
			}

			nost = 0;
			used_row = 0;
			num++;
		}
	}

	return 0;
}

void push( const int depar, int st_nth, int rt_nth, const int depth )
{
	int i;
	int rt_using = 0;

	if( route[rt_nth][0] == 0 )
	{
		route[rt_nth][0] = depar;
		rt_using = 1;
	}
	if( route[rt_nth][11] < depth )
	{
		route[rt_nth][11] = depth;
	}

	for( i = 0; i < 10; i++ )
	{
		if( route[rt_nth][i] == 0 )
		{
			break;
		}
	}

	route[rt_nth][i] = ary[st_nth][1];
	route[rt_nth][10] += ary[st_nth][2];
	used_row += rt_using;
}

int findroute( const int departure, int destination, int depth )
{
	int i, j, k;
	int sentinel = 0;

	if( depth >= intersection )
	{
		return -1;
	}

	for( i = 0; (ary[i][0] != 0) && (i < nost); i++ )
	{
		if( ary[i][1] == destination )
		{
			if( ary[i][0] == departure )
			{
				push( departure, i, used_row, depth );
			}
			else
			{
				sentinel = findroute( departure, ary[i][0], depth + 1 );

				if( sentinel == -1 )
				{
					sentinel = 0;
					continue;
				}

				for( j = 0; (route[j][0] != 0) && (j < MROUTE); j++ )
				{
					if( route[j][route[j][11]] == 0 )
					{
						for( k = route[j][11]; k > 0; k-- )
						{
							if( route[j][k] != 0 )
							{
								break;
							}
						}

						if( route[j][k] == ary[i][0] )
						{
							push( departure, i, j, depth );
						}
					}
				}
			}
		}
	}

	return 0;
}

탐색 방법은 대강 이런식입니다

만들면서 방법이 조금 바뀌긴 했지만;

글로 쓰려고 했는데 정리가 잘 안돼서 그냥 엑셀로 -_-a (크게해서 보세요)

[sample input #1]