208 - Firetruck

[Scarecrow]

Thanks ! Didn't know this info!

[metaphysis]

Five times of P.E.
The sampe output in problem statement PDF is wrong.
Correct ouput format(if the number of routes is 1, you should output "1 routes", after every streetcorner just print ONE space):

Code: Select all

CASE 1:
1 2 3 4 6
1 2 3 5 6
1 2 4 3 5 6
1 2 4 6
1 3 2 4 6
1 3 4 6
1 3 5 6
There are 7 routes from the firestation to streetcorner 6.
CASE 2:
1 3 2 5 7 8 9 6 4
1 3 4
1 5 2 3 4
1 5 7 8 9 6 4
1 6 4
1 6 9 8 7 5 2 3 4
1 8 7 5 2 3 4
1 8 9 6 4
There are 8 routes from the firestation to streetcorner 4.

[efrshuvo]

I am really confused. For every testcase here and uDebug my code gives the correct answer but i am getting WA all the time. can any body help me to find the bug or any critical input / out put for debug?

Code: Select all

//208 Firetruck
//https://uva.onlinejudge.org/external/2/208.pdf

#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>

#define MAX 22
#define MAXNODE 100
#define INFINITY 32767

int addj[MAXNODE][MAXNODE];
int visited[MAXNODE][MAXNODE];
int path[1000];
int trout = 0;
int vist[MAXNODE];
int dist[MAXNODE][MAXNODE];
void init()
{
	for (int i = 0; i <= MAXNODE; i++)
	{
		path[i] = 0;
		vist[i] = 0;
		for (int j = 0; j <= MAXNODE; j++)
		{
			addj[i][j] = visited[i][j] = 0;
			dist[i][j] = INFINITY;
		}

	}
}

void foloyd_warshal(int maxnode)
{
	for (int i = 0; i <= maxnode; i++)
	{
		dist[i][i] = 0;
	}

	for (int k = 0; k <= maxnode; k++)
	{
		for (int i = 0; i <= maxnode; i++)
		{
			for (int j = 0; j <= maxnode; j++)
			{
				if (dist[i][j] > dist[i][k] + dist[k][j])
				{
					dist[i][j] = dist[i][k] + dist[k][j];
				}
			}

		}
	}
}




void find_rout(int node,int firecorner,int maxnode,int index)
{
	int np = 0;
	if (node == firecorner)
	{
		//printf("   ");
		int i = 0;
		for (i = 0; i < index-1; i++)
			printf("%d ",path[i]);
		printf("%d", path[i]);
		printf("\n");
		trout++;
		return ;
	}
	for (int v = 0; v <= maxnode; v++)
	{
		if (((addj[node][v]) && (!vist[v])) && (dist[firecorner][v]<INFINITY))
		{
			visited[node][v] = 1;
			path[index] = v;
			np = v;
			vist[v] = 1;
			find_rout(np, firecorner, maxnode, index + 1);
			vist[np] = 0;
			/*if (np>2)
				vist[np] = 0;*/
		}
	}
}

int main()
{
	int firecorner = 0,case1=1;
	int u, v,maxnode;
	/*freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);*/

	while (scanf("%d", &firecorner) != EOF)
	{
		maxnode = 0;
		trout = 0;
		init();
		while (1)
		{
			scanf("%d %d", &u, &v);
			if (u == 0 && v == 0)
				break;
			addj[u][v] = 1;
			addj[v][u] = 1;
			dist[u][v] = 1;
			dist[v][u] = 1;
			if (maxnode < u)
				maxnode = u;
			if (maxnode < v)
				maxnode = v;
		}
		foloyd_warshal(maxnode);
		path[0] = 1;
		vist[1] = 1;
		printf("CASE %d:\n", case1++);
		find_rout(1, firecorner,maxnode,1);
		printf("There are %d routes from the firestation to streetcorner %d.\n", trout,firecorner);
	}

	return 0;
}

[lighted]

Try running your code on the sample input. Your code doesn't match the sample output.