/* Xet so do gòm n nút giao thông danh sô tù 1 -> n và m doan duong nói chúng, môi doan duong nói 2 nút giao thông s và d. Hãy nhap du lieu vè mang luoi giao thông dó, nhap só hieu 2 nút giao thông s và d. Hay in ra tat ca các cách di tù s tói d và môi cách di không dc qua nút giao thông nào quá 1 làn.*/#include <iostream>#include <conio.h>#include <iomanip>#include <cstdio>using namespace std;const int size = 100;int maxE = 100;int maxC = size * maxE;int C[size][size]; /*Ma tran chi phí*/int X[size+1], BestWay[size+1]; /*X de thu kha nang, BestWay de ghi nhan nghiem*/int T[size]; /*De luu chi phí tù X[1] -> X[i]*/bool FREE[size];int MinSpending; /*chi phí hành trình tói uu*/int M,N;void Enter(){ int i,j,k; cout << " CITY: " ; cin >> N; cout << " TRAFFIC ROAD: "; cin >> M; for ( i = 1; i <= N; i++ ) /*Khoi tao bang chi phí */ { for ( j = 1; j <= N; j++ ) { if ( i == j ) C[i][j] = 0; else C[i][j] = maxC; } } for ( int k = 1; k <= M; k++ ) { cout << "From : "; cin >> i; cout << "to --> : "; cin >> j; cout << "The Fee will cost : "; cin >> C[i][j]; C[j][i] = C[i][j]; /*Chi phí là nhu nhau tren 2 chièu */ }}void InI(){ for ( int i = 1; i <= N; i++ ) { FREE[i] = true; } FREE[1] = false; /*Các TP là chua di qua ngoai trù TP 1*/ X[1] = 1; /*Xuat phat tù TP 1*/ T[1] = 0; /*Chi phí tai TP xuat phat là 0*/ MinSpending = maxC;}void PRINT(){ if ( MinSpending == maxC ) { cout << "NO SOLUTION "; } else { for ( int i = 1; i <= N; i++ ) { cout << BestWay[i] << "->"; } cout << " Minimum Spending is : " << MinSpending; }}void BACKTRACK ( int i ){ for ( int j = 2; j <= N; j++ ) /*Thu các TP tù 2 -> N*/ { if ( FREE[j] == true ) /*Néu chua gap TP di qua*/ { X[i] = j; /*Thu di*/ T[i] = T[i-1] + C[X[i-1]][j]; /*Chi phí = Chi phí buóc truóc + chi phí duòng di truc tiep*/ } else { if ( T[i] < MinSpending )/*Hien nhien néu có dièu này thì C[x-1][j] < +oo ròi*/ { if ( i < N ) /*Néu chua dén duoc N*/ { FREE[j] = false; /*Dánh dáu TP vùa thu*/ BACKTRACK ( i + 1 ); /*Tìm kha nang chon x[i+1]*/ FREE[j] = true; /*Bo dánh dáu*/ } } else { if ( ( T[N] + C[X[N]][1] ) < MinSpending ) /*Tù x[N] quay lai 1 van tón chi phí ít hon truóc */ { /*Cap nhat BestConfig */ for ( int var = 1; var <= N; var++ ) { BestWay[var] = X[var]; } MinSpending = T[N] + C[X[N]][1]; } } } }}int main(){ Enter(); InI(); BACKTRACK (2); PRINT(); system ("pause");}