10296 - Jogging Trails

All about problems in Volume 102. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10296 - Jogging Trails

Post by Ghost77 dimen » Wed Jul 02, 2003 7:55 am


Any suggestions?

Thanks for your help. :D

gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:

Post by gvcormac » Fri Jul 11, 2003 4:04 pm

Look up "Chinese Postman."

farzane
New poster
Posts: 26
Joined: Thu Jun 15, 2006 9:26 am

Post by farzane » Fri Aug 25, 2006 4:21 pm

I'm getting TLE on this problem.please help?Is my algorithm rigth?

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

Post by DD » Mon Apr 25, 2011 4:09 am

farzane wrote:I'm getting TLE on this problem.please help?Is my algorithm rigth?

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. :D
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

Post by verngutz » Sun Oct 20, 2013 7:48 pm

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

Post by Repon kumar Roy » Tue Oct 28, 2014 11:13 pm

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: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 10296 - Jogging Trails

Post by lighted » Wed Oct 29, 2014 12:39 am

Hey Repon kumar Roy! That is accepted code! Problems with copy/paste? :D
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: 138
Joined: Wed May 18, 2011 3:04 pm

Re: 10296 - Jogging Trails

Post by metaphysis » Wed Apr 04, 2018 4:16 am

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;
}

Post Reply

Return to “Volume 102 (10200-10299)”