![:)](./images/smilies/icon_smile.gif)
208 - Firetruck
Moderator: Board moderators
-
- 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):
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.
metaphysis: http://uhunt.onlinejudge.org/id/95895
My solutions for UVa problems: https://github.com/metaphysis/Code.
My solutions for UVa problems: https://github.com/metaphysis/Code.
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 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;
}
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