## 208 - Firetruck

Moderator: Board moderators

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

### Re: 208 Why Time Limit Exceeded

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

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

### Re: 208 - Firetruck

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
New poster
Posts: 4
Joined: Thu Nov 08, 2012 9:25 am

### Re: 208 - Firetruck

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 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++)
{
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;
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: 587
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 208 - Firetruck

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