Assignment $2\mathrm{.}1$ #include

#include

#include

using namespace std;

$//$ Global variables are replaced by user inputs

int n; $//$ Number of cities

vector$>$ dist; $//$ Distance matrix

int allCityVisited; $//$ Updated after input

int travellingSalesman$($int visited$\_$cities, int currCity, vector$>$& min$\_$distance$)\{$

if$($visited$\_$cities $==$ allCityVisited$)\{$

return dist$[$currCity$][0]$; $//$ dist to return back to starting vertex $0$

$\}$

if$($min$\_$distance$[$visited$\_$cities$][$currCity$]!=-1)\{$

return min$\_$distance$[$visited$\_$cities$][$currCity$]$;

$\}$

int ans $=$ INT$\_$MAX;

for$($int city $=0$; city $$ n; city$++)\{$

if$(($visited$\_$cities & n;

dist.resize$($n$,$ vector$($n$))$;

allCityVisited dist$[$i$][$j$]$;

$\}$

$\}$

vector$>$ min$\_$distance$(1<mi>(</mi>$n$,-1))$;

$//$ Starting from city $0,$ with visited cities bitmask as $1$ for city $0$

int shortestDistance $=$ travellingSalesman$(1,0,$ min$\_$distance$)$;

cout $$ "The shortest distance to visit all the cities is $"$ shortestDistance $$ endl;

return $0$;

$\}$