208 - Firetruck

[10153EN]

I feel exhausted about this problem. I am quite sure I have implemented a correct algorithm to this problem, which handled all cases, at least for those I thought of.

Could the problem setter give me a clear image on the problem description? Since the problem description is not clear enough, for example how to handle some special cases.
1. What if the nearest corner is #1, i.e. the firestation? Should I output 1 route or 0 route?
2. What's the output format in detail? Are the numbers of width 4? Should I obmit the 's' when there's only 1 route?

[Christian Schuster]

http://www.acm.inf.ethz.ch/ProblemSetAr ... 1/acm91a.c

This is the "official" backtracking solution, which should make the output format clearer, but don't try it on Valladolid, it gets TLE.

[Shih-Chia Cheng]

I feel confused with this problem, too.
I don't know why I always get TLE.......
Since we need to enumerate all possible paths. Can we come up with a better solution than backtracking?
So many doyens tried to solve this problem, but in vain.
Is there anything wrong with input or output... ?

[Adrian Kuegel]

I can't think of a solution without backtracking, but perhaps one can find some break conditions to avoid trying a path which does not lead to the fire.
I think the "official" solution is not very good, at least my solution is faster, and I get TLE, too.

[wyvmak]

ans to 10153EN:
1. if the nearest corner is #1, only 1 route, ie. "1"
2. i output "1 routes". but i get P.E. and seems all justified with width 4 cannot get me AC.

[Dominik Michniewski]

Does anyone know faster method than simple DFS to solve this problem ?
I use DFS in my solution, but got TLE .... Could anyone help me ?

[Adrian Kuegel]

Try to avoid using edges that does not lead to the destination. Use only edges that you have not used or that lead to a street corner from wich a path is known.

[Dominik Michniewski]

That means, that I could use kind of DP algorithm ? not full DFS ?

Thanks Adrian .... i try to change my code later now I must working ...

[xenon]

BTW: Firetruck is #208

[Dominik Michniewski]

Xenon, you have absolutely right !!
I must be tired at morning, when I post this message .... to hot for me (and my comp too ... )

[xenon]

No problem
I had a long standing TLE on this problem too. Adrian's hints made me look at the code again, and make some adjustments.
Now I have WA in 0.000 seconds! So obviously the code is bad in some cases, although it still solves the examples.
Any tips?

[Whinii F.]

Adrian's idea is absolutely COOL! Never thought about that and was wondering why would I get a TLE.. so, the judging data should include one like:
2
1 2
1 3
1 4
..
1 20

.. and nodes from 3 to 20 form a completed graph. Huh
Learned a lot from this problem. Thanks!

[obayashi]

i got TLE too with this problem at first. my friend gave me some hints.
first, use floyd or warshall to determine whether the node is reachable to the destination while using dfs... then i got AC...

[Even]

No problem
I had a long standing TLE on this problem too. Adrian's hints made me look at the code again, and make some adjustments.
Now I have WA in 0.000 seconds! So obviously the code is bad in some cases, although it still solves the examples.
Any tips?

1... if you use link list... you should sort it first
2... if input like

1
2 3
2 4
3 3
0 0

output is

1
There are 1 routes from the firestation to streetcorner 1.

[LTH]

I have done what u had said and i still cant past the judge....
can anyone give me more special cases?? Thanks

The following is my code(i will appreciate very much if u can point out my mistakes):

[cpp]
#include <stdio.h>
#include <stdlib.h>
#define MAX 22


int i,j,k,t,m,cnt,tar,num,count,a,b,tmp,map[MAX][MAX],n[MAX],p[MAX][MAX],ans[MAX];
int next[MAX][MAX],nu[MAX];
bool used[MAX],l,d[MAX];

void dfs2(int x)
{
int e,f;
used[x]=1;
ans[tmp++]=x;
if(x==tar)
{
for(e=0;e<tmp;e++)
{
if(e>0)
printf(" ");
printf("%d",ans[e]);
}
printf("\n");
tmp--;
used[x]=0;
count++;
return ;
}
for(e=0;e<nu[x];e++)
{
if(!used[next[x][e]])
dfs2(next[x][e]);
}
tmp--;
used[x]=0;
}

void dfs(int x)
{
int e,f,g;
used[x]=1;
if(x==1)
{
used[x]=0;
return;
}
for(e=0;e<n[x];e++)
{
if(!used[p[x][e]])
{
for(f=0,g=0;f<nu[p[x][e]];f++)
{
if(next[p[x][e]][f]==x)
{
g=1;
break;
}
}
if(g==0)
{
next[p[x][e]][nu[p[x][e]]++]=x;
dfs(p[x][e]);
}
}
}
used[x]=0;
}

int presort(const void *m1, const void *m2)
{
return *((int*)m1)-*((int*)m2);
}

void main()
{
cnt=0;
while(scanf("%d",&tar)!=EOF)
{
for(i=0;i<MAX;i++)
for(j=0;j<MAX;j++)
map[j]=0;
for(i=1;i<MAX;i++)
map=1,used=0,nu=0,d=0,n=0;
while(1)
{
scanf("%d %d",&a,&b);
if(a==0&&b==0)
break;
map[a]=1,map[a]=1;
}
d[1]=1;
for(i=1;i<MAX;i++)
{
for(j=1,t=0;j<MAX;j++)
{
if(d[j]&&!used[j])
{
t=j;
break;
}
}
used[t]=1;
for(j=1;j<MAX;j++)
if(map[t][j])
d[j]=1,p[j][n[j]++]=t;
}
for(i=1;i<MAX;i++)
used=0;
printf("CASE %d:\n",++cnt);
count=0,tmp=0;
dfs(tar);
for(i=1;i<MAX;i++)
if(nu>0)
qsort(next,nu[i],sizeof(int),presort);
dfs2(1);
printf("There are %d routes from the firestation to streetcorner %d.\n",count,tar);
}
}
[/cpp]