DrumExpress 🇷🇴

#include <iostream> #include <fstream> using namespace std; int x[10],v[50][50],i,n,j, tras[10],dist=0; ifstream f("retea.in"); void INIT(int k) { x[k]=1; } int EXISTA(int k) { if(x[k]<n) return 1; else return 0; } int VALID(int k) { int d; for(int i=1;i<k;i++) if(x[i]==x[k]) return 0; // nodurile sa nu se repete if(k==n) if(v[x[k]][1]==0) return 0; // verific daca exista muchie intre ultimul nod si primul if(v[x[k-1]][x[k]]==0) return 0; // verif daca exista muchie intre 2 noduri din lista else if(dist!=0) // daca nu exista muchie si nu ma aflu la primul traseu {d=0; for(int i=2;i<=k;i++) // calculez distanta de la primul nod ales d=d+v[x[i-1]][x[i]]; // pana la punctul k if(d>dist) return 0; // daca distanta calculata este mai mare decat dist minima gasita } return 1; } int SOLUTIE(int k) { if(k==n) return 1; else return 0; } void OPTIM(int k) { int d=0; for(int i=2;i<=k;i++) // calculez distanta de la primul nod ales d=d+v[x[i-1]][x[i]]; // pana la punctul k d=d+v[x[k]][x[1]]; // adaug ultima muchie (care inchide ciclul) if((dist>d)||(dist==0)) // daca distanta calc este mai mica decat d sau prima solutie { dist=d; // retin distanta for(int i=1;i<=k;i++) // si traseul tras[i]=x[i]; } } void BCK() { int k=2; INIT(k); while (k>1) if(EXISTA(k)) { x[k]++; if(VALID(k)) if(SOLUTIE(k)) OPTIM(k); else {k++; INIT(k);} } else k--; } int main() { f>>n; for(i=1;i<=n;i++) for(j=1;j<=n;j++) f>>v[i][j]; x[1]=1; BCK(); // afisare tras[] si dist }