#include <stdio.h>
#include <limits.h>
#define V 5 // Number of vertices
int graph[V][V] = {
{0, 2, 0, 12, 5},
{2, 0, 4, 8, 0},
{0, 4, 0, 3, 3},{12, 8, 3, 0, 10},
{5, 0, 3, 10, 0}
};
int visited[V];
int path[V];
int min_cost = INT_MAX;
int final_path[V];
void copy_path() {
for (int i = 0; i < V; i++)
final_path[i] = path[i];
final_path[V] = path[0];
}
void tsp(int curr, int count, int cost) {
if (count == V && graph[curr][0]) {
if (cost + graph[curr][0] < min_cost) {
min_cost = cost + graph[curr][0];
copy_path();
}
return;
}for (int i = 0; i < V; i++) {
if (!visited[i] && graph[curr][i]) {
visited[i] = 1;
path[count] = i;
tsp(i, count + 1, cost + graph[curr][i]);
visited[i] = 0;
} } }
int main() {
visited[0] = 1;
path[0] = 0;
tsp(0, 1, 0);
printf("Minimum cost: %d\n", min_cost);
printf("Path: ");
for (int i = 0; i <= V; i++)
printf("%c ", 'A' + final_path[i]);
printf("\n");
return 0;
}