Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <stdio.h>
- #include <limits.h>
- using namespace std;
- #define MAXN 20
- int n, c[MAXN][MAXN] = {}, x[MAXN], xopt[MAXN];
- int fk, fopt = INT_MAX , cmin = INT_MAX;
- void input(){
- cin >> n;
- for(int i = 1; i <= n; i++)
- for(int j = 1; j <= n; j++){
- cin >> c[i][j];
- if (i != j)
- cmin = cmin > c[i][j] ? c[i][j]:cmin;
- }
- }
- int UCV(int y, int k){
- for(int i = 2; i < k; i++)
- if (y == x[i]) return 0;
- return 1;
- }
- void TRY(int k){
- for(int y = 2; y <= n; y++){
- if (UCV(y, k)){
- x[k] = y;
- fk += c[x[k-1]][y];
- if (k == n){
- if (fk + c[x[k]][1] < fopt){
- fopt = fk + c[x[k]][1];
- for(int i = 1; i <= n; i++)
- xopt[i] = x[i];
- }
- } else
- if (fk + cmin * (n - k + 1) < fopt) TRY(k + 1);
- fk -= c[x[k-1]][y];
- }
- }
- }
- int main(){
- freopen("input.txt", "r", stdin);
- input();
- x[1] = 1; fk = 0;
- TRY(2);
- for (int i = 1; i <= n; i++)
- cout << xopt[i] << " -> ";
- cout << " 1 " << endl;
- cout << "min cost = " << fopt << endl;
- return 0;
- }
- INPUT e.g:
- 5
- 0 3 14 18 15
- 3 0 4 22 20
- 17 9 0 16 4
- 9 20 7 0 18
- 9 15 11 5 0
Advertisement
Add Comment
Please, Sign In to add comment