## 10296 - Jogging Trails

Moderator: Board moderators

Ghost77 dimen
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan

### 10296 - Jogging Trails

Any suggestions?

gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:
Look up "Chinese Postman."
farzane
New poster
Posts: 26
Joined: Thu Jun 15, 2006 9:26 am

Code: Select all

``````#include<iostream.h>

int n,v,e,shortest[20][20],G[20][20],d[20],sum,minsum,A[20],degree[20];
bool sw[20],put[20],chosen[20];

void shortpath(){
int a,cur,i,no,min;
for(a=1;a<=v;a++){
if(degree[a]%2==0)continue;
for(i=1;i<=v;i++){
sw[i]=true;
d[i]=-1;
}
d[a]=0;
cur=a;
sw[cur]=false;
no=1;

while(no<v){
for(i=1;i<=v;i++){
if(sw[i])
if(G[cur][i]!=0)
if(G[cur][i]+d[cur]<d[i]||d[i]==-1)
d[i]=G[cur][i]+d[cur];
}
min=sum;
for(i=1;i<=v;i++)
if(sw[i]&&d[i]<min&&d[i]!=-1){
min=d[i];
cur=i;
}
sw[cur]=false;
no++;
}
for(i=1;i<=v;i++)
shortest[a][i]=shortest[i][a]=d[i];

}
}

void jaygasht(int size,int cursum){
if(size%2==0){
if(size!=0 && A[size]>A[size-1])return;
cursum+=shortest[A[size]][A[size-1]];
}

if(cursum>=minsum)return;

if(size==n)
if(cursum<minsum){
minsum=cursum;
cursum-=shortest[A[size]][A[size-1]];
return;
}
for(int i=1;i<=v;i++)
if(!put[i]){
A[size+1]=i;
put[i]=true;
jaygasht(size+1,cursum);
put[i]=false;
}
}

void computemin(){
for(int i=1;i<n;i++)
put[i]=false;

jaygasht(0,0);
}

void main(){
int i,j,oddno,odd[20],x[1000],y[1000],w[1000];
cin>>v;
while(v!=0){
cin>>e;
for(i=1;i<=v;i++)
for(j=1;j<=v;j++)
G[i][j]=0;
for(i=1;i<=v;i++)
degree[i]=0;

sum=0;
for(i=0;i<e;i++){
cin>>x[i]>>y[i]>>w[i];
sum+=w[i];
degree[x[i]]++;
degree[y[i]]++;
if(G[x[i]][y[i]]==0)
G[x[i]][y[i]]=G[y[i]][x[i]]=w[i];
else
if(G[x[i]][y[i]]>w[i])
G[x[i]][y[i]]=G[y[i]][x[i]]=w[i];
}
oddno=0;
for(i=1;i<=v;i++)
if(degree[i]%2==1)
odd[oddno++]=i;
n=v;
if(v%2==1)
n--;

shortpath();

minsum=sum;
for(i=0;i<oddno;i++)
chosen[i]=false;

computemin();

cout<<sum+minsum<<endl;
cin>>v;
}
}

``````
DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

### Re: 10296 - Jogging Trails

Code: Select all

``````#include<iostream.h>

int n,v,e,shortest[20][20],G[20][20],d[20],sum,minsum,A[20],degree[20];
bool sw[20],put[20],chosen[20];

void shortpath(){
int a,cur,i,no,min;
for(a=1;a<=v;a++){
if(degree[a]%2==0)continue;
for(i=1;i<=v;i++){
sw[i]=true;
d[i]=-1;
}
d[a]=0;
cur=a;
sw[cur]=false;
no=1;

while(no<v){
for(i=1;i<=v;i++){
if(sw[i])
if(G[cur][i]!=0)
if(G[cur][i]+d[cur]<d[i]||d[i]==-1)
d[i]=G[cur][i]+d[cur];
}
min=sum;
for(i=1;i<=v;i++)
if(sw[i]&&d[i]<min&&d[i]!=-1){
min=d[i];
cur=i;
}
sw[cur]=false;
no++;
}
for(i=1;i<=v;i++)
shortest[a][i]=shortest[i][a]=d[i];

}
}

void jaygasht(int size,int cursum){
if(size%2==0){
if(size!=0 && A[size]>A[size-1])return;
cursum+=shortest[A[size]][A[size-1]];
}

if(cursum>=minsum)return;

if(size==n)
if(cursum<minsum){
minsum=cursum;
cursum-=shortest[A[size]][A[size-1]];
return;
}
for(int i=1;i<=v;i++)
if(!put[i]){
A[size+1]=i;
put[i]=true;
jaygasht(size+1,cursum);
put[i]=false;
}
}

void computemin(){
for(int i=1;i<n;i++)
put[i]=false;

jaygasht(0,0);
}

void main(){
int i,j,oddno,odd[20],x[1000],y[1000],w[1000];
cin>>v;
while(v!=0){
cin>>e;
for(i=1;i<=v;i++)
for(j=1;j<=v;j++)
G[i][j]=0;
for(i=1;i<=v;i++)
degree[i]=0;

sum=0;
for(i=0;i<e;i++){
cin>>x[i]>>y[i]>>w[i];
sum+=w[i];
degree[x[i]]++;
degree[y[i]]++;
if(G[x[i]][y[i]]==0)
G[x[i]][y[i]]=G[y[i]][x[i]]=w[i];
else
if(G[x[i]][y[i]]>w[i])
G[x[i]][y[i]]=G[y[i]][x[i]]=w[i];
}
oddno=0;
for(i=1;i<=v;i++)
if(degree[i]%2==1)
odd[oddno++]=i;
n=v;
if(v%2==1)
n--;

shortpath();

minsum=sum;
for(i=0;i<oddno;i++)
chosen[i]=false;

computemin();

cout<<sum+minsum<<endl;
cin>>v;
}
}

``````
You can use memorization to speed up.
Have you ever...
• Wanted to work at best companies?
• Struggled with interview problems that could be solved in 15 minutes?
• Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.
verngutz
New poster
Posts: 1
Joined: Sun Oct 20, 2013 7:40 pm

### Re: 10296 - Jogging Trails

Please help. I keep getting WA. I am trying to solve this problem using the Chinese Postman algorithm. I use the Hungarian method to find out which nodes to pair up. Is there something wrong with this approach? Any special cases I have to be wary of?
Repon kumar Roy
Learning poster
Posts: 96
Joined: Tue Apr 23, 2013 12:54 pm

### Re: 10296 - Jogging Trails

I used Chineese Postman Algo
And floyd Warshall to to find the minimal distance
Last edited by Repon kumar Roy on Wed Oct 29, 2014 1:24 pm, edited 1 time in total.
lighted
Guru
Posts: 587
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 10296 - Jogging Trails

Hey Repon kumar Roy! That is accepted code! Problems with copy/paste?
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman
metaphysis
Experienced poster
Posts: 139
Joined: Wed May 18, 2011 3:04 pm

### Re: 10296 - Jogging Trails

Test data generator.

Code: Select all

``````#include <bits/stdc++.h>

using namespace std;

int main(int argc, char *argv[])
{
srand(time(NULL));
for (int cases = 1; cases <= 25; cases++)
{
int n = rand() % 15 + 2, m = rand() % 500 + n;
m = min(n * 20, m);
cout << n << ' ' << m << '\n';
for (int i = 1; i < n; i++)
cout << i << ' ' << (i + 1) << ' ' << (rand() % 10000 + 1) << '\n';
cout << 1 << ' ' << n << ' ' << (rand() % 10000 + 1) << '\n';
for (int i = n + 1; i <= m; i++)
{
int x = rand() % n + 1, y = rand() % n + 1;
cout << x << ' ' << y << ' ' << (rand() % 10000 + 1) << '\n';
}
}
cout << 0 << '\n';
return 0;
}
``````