208 - Firetruck

All about problems in Volume 2. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Scarecrow
Learning poster
Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

Re: 208 Why Time Limit Exceeded

Post by Scarecrow » Thu Feb 14, 2013 12:14 pm

Thanks :) ! Didn't know this info!
Do or do not. There is no try.

metaphysis
Experienced poster
Posts: 113
Joined: Wed May 18, 2011 3:04 pm

Re: 208 - Firetruck

Post by metaphysis » Tue Apr 26, 2016 5:28 pm

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.
My solutions for UVa problems: https://github.com/metaphysis/Code.

efrshuvo
New poster
Posts: 4
Joined: Thu Nov 08, 2012 9:25 am

Re: 208 - Firetruck

Post by efrshuvo » Wed Aug 10, 2016 9:34 am

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
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 208 - Firetruck

Post by lighted » Mon Mar 13, 2017 4:07 pm

Try running your code on the sample input. Your code doesn't match the sample output.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Post Reply

Return to “Volume 2 (200-299)”