## 302 - John's trip

Moderator: Board moderators

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.
I got Accepted after got WA many times.

If you are trying to solve it, you must realize:

There are something wrong in this problem.

The street number can be large than 44. ( I think it is less than 2000 )

And John lives at the street of the first line of each data block.
not the "number 1" street!

and you can just use DFS to solve it.
or you can use euler cycle method.
Mr.south
New poster
Posts: 11
Joined: Thu Jan 25, 2007 1:45 pm

### help 302

i use eulerian circuit to solve this question
but i got a problem
I have some problem when i got a vertex, this vertex has more than two edges, my code will choose the smallest num of vertex to put in the stack, but i think this is wrong

ex. when i got node 2, this node has edge 1, 2, 3, 4, 5. what edge should i choose and push the related vertex in the stack

this is part of my code

void find_circuit(int i)
{
int j, min;

if(degree == 0)
{
push(stack, i);
return;
}
for(j=0;j<45;j++) // check the whole neighbors
{
if(adj[j] > 0) //there exist more than 1 edges
{
if(visited[j] > 0) visited[j]--; //i use this to check whether the graph is connected
adj[j]--; //kill one edge (i, j) (j, i)
degree--;
degree[j]--;
find_circuit(j);
}
}
push(stack, i);
}
porker2008
New poster
Posts: 21
Joined: Wed Oct 08, 2008 7:04 am

### Why 302 TLE?

I have solved 302 by using DFS Algorithm. However, I get TLE.

I don't know what kind of cases will lead to TLE. Can somebody tell me.

I find my program run fast on my computer even though the cases are very complicated.

I think I must ignore some special cases that beyond my thinking.
porker2008
New poster
Posts: 21
Joined: Wed Oct 08, 2008 7:04 am

### Re: Why 302 TLE?

Code: Select all

``````#include<iostream>
#include<vector>
using namespace std;

void check(int i,int loc);

vector<int> a1,a2,street;
int order;
bool finish=false,pass=false;
int num;
bool used;
bool checked;

int main(){
int b1,b2,st;
while(cin>>b1>>b2){
a1.clear(); a2.clear(); street.clear();
if(b1==0&&b2==0) break;
a1.push_back(b1);
a2.push_back(b2);
cin>>st;
street.push_back(st);
while(cin>>b1>>b2){
if(b1==0&&b2==0) break;
a1.push_back(b1);
a2.push_back(b2);
cin>>st;
street.push_back(st);
}
num=street.size();
memset(used,0,sizeof(used));
int loc=min(a1,a2);
finish=false;
pass=false;
memset(order,0,sizeof(order));
check(0,loc);
if(pass){
for(int i=0;order[i]!=0;i++) {cout<<order[i]; if(order[i+1]!=0) cout<<" ";}
cout<<endl<<endl;
}
else
cout<<"Round trip does not exist."<<endl<<endl;
}
return 0;
}
//Using DFS to find the order.
void check(int i,int loc){
if(i==street.size()&&loc==min(a1,a2)){pass=true;finish=true;return;}
int min=-1;
int tmin=2000;
int num=0;
for(int j=0;j<street.size();j++)
if(!used[j]&&(a1[j]==loc||a2[j]==loc)) num++;
for(int k=0;k<num&&!pass&&!finish;k++){
int tmin=2000;
int l=2000;
for(int j=0;j<street.size();j++)
if(!used[j]&&(a1[j]==loc||a2[j]==loc)&&street[j]>min&&street[j]<tmin) {tmin=street[j];l=j;}
min=street[l];
used[l]=true;
if(l==2000) {break;}
if(a1[l]==loc) {order[i]=street[l]; check(i+1,a2[l]);}
else {order[i]=street[l]; check(i+1,a1[l]);}
used[l]=false;
if(!pass) order[i]=0;
}
return;
}
``````
sami001
New poster
Posts: 3
Joined: Thu Jun 17, 2010 5:19 pm

### Re: 302 (John's trip) test cases

i'm getting RTE... pls... somebody help me::

Code: Select all

``````#include <stdio.h>

int main()
{

int j1,j2,r,i,k,a,b,c,H,m,n,p,p1,sum,j,q,l,s,t,u,junc,result,search,flag,mem;

while(1){

int g={0},g1={0};
a=0;
b=0;
n=0;
flag=0;

for(i=0;;i++)
{

scanf("%d %d",&j1,&j2);
if(j1==0 && j2==0 && i==0){n=1;break;}
else if(j1==0 && j2==0)break;
scanf("%d",&r);

if(i==0)
{
if(j1>j2)H=j2;
else H=j1;
}

if(j1!=j2)
{
g[j1][r]=g1[j1][r]=1;
g[j2][r]=g1[j2][r]=1;
}

else if(j1==j2)
{
g[j1][r]=g1[j1][r]=2;
g[j2][r]=g1[j2][r]=2;
}

if(r>a)a=r;
if(j1>b)
{
b=j1;
if(j2>j1)b=j2;
}
}

if(n==1)break;
n=0;

for(i=1;i<=b;i++)
{
sum=0;
for(k=1;k<=a;k++)sum+=g[i][k];
if(sum%2==1){printf("Round trip does not exist.\n");printf("\n");n=1;break;}
}

if(n==1)continue;
i=H;
m=a+1;
junc=H;

p=0;
s=0;

while(p!=a)
{

search=0;
if(flag==1)mem=result[p+1];

n=0;
q=0;

for(j=1;j<=a;j++)if(g[i][j]==1)n++;

if(n<=1)
{
for(j=1;j<=a;j++)if(g[i][j]==2)
{
result[p+1]=j;
g[i][j]=0;
p++;
q=1;
search=1;
}

}

n=0;

for(j=1;j<=a;j++){

if(j==m)continue;

if(g[i][j]==1)
{

if(q==0){
for(k=1;k<=a;k++){
if(g[i][k]==2 && k<j){g[i][k]=0;result[p+1]=k;search=1;p++;}
else if(g[i][k]==2 && k>j)break;
}
}
result[p+1]=j;
p++;
search=1;
l=i;
for(i=1;i<=b;i++)g[i][j]=0;

break;
}
}

if(search==0){
s--;
i=junc[s];
m=1;
if(flag==0)p1=p;

flag=1;

p=junc[s];
continue;
}

else if(search==1 && flag==1){

for(t=p1;t>=p+1;t--){
c=result[t];
for(u=1;u<=b;u++)g[u][c]=g1[u][c];
}
for(u=1;u<=b;u++)g[u][mem]=g1[u][mem];

flag=0;
}

m=j;
for(k=1;k<=b;k++){
if(g1[k][j]==1 && k!=l)i=k;
}

s++;
junc[s]=i;
junc[s]=p;
}

for(s=1;s<=a;s++)
{
if(s<a)printf("%d ",result[s]);
else printf("%d\n\n",result[s]);
}

}

return 0;

}
``````
dibery
Learning poster
Posts: 76
Joined: Sat Feb 23, 2013 4:16 pm
Location: Taiwan, Taipei
Contact:

### Re: 302 - John's trip

Note that the "lexicographical order" is not what we used for strings.
Rather, it's for numeric values.
For example, if "9 10" & "10 9" are both solutions, we should print "9 10" instead of "10 9" because 9 goes before 10.
Life shouldn't be null.