10296 - Jogging Trails

[Ghost77 dimen]

Any suggestions?

Thanks for your help.

[gvcormac]

Look up "Chinese Postman."

[farzane]

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]

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.

[verngutz]

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]

I used Chineese Postman Algo
And floyd Warshall to to find the minimal distance

[lighted]

Hey Repon kumar Roy! That is accepted code! Problems with copy/paste?

[metaphysis]

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