Any suggestions?
Thanks for your help.

Moderator: Board moderators
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.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; } }
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;
}