#include <bits/stdc++.h>

using namespace std;

int DT[9][9] = {
	{-1, -1, 16, 10, 19, -1, -1, -1, -1},
	{-1, -1, -1, -1, -1, 3, 8, 12, 5},
	{16, -1, -1, 18, -1, -1, -1, 20, -1},
	{10, -1, 18, -1, 7, 7, 8, -1, -1},
	{19, -1, -1, 7, -1, -1, -1, -1, 9},
	{-1, 3, -1, 7, -1, -1, 2, 15, -1},
	{-1, 8, -1, 8, -1, 2, -1, -1, 4},
	{-1, 12, 20, -1, -1, 15, -1, -1, -1},
	{-1, 5, -1, -1, 9, -1, 4, -1, -1}
};

int start_step = 0; //A
int stop_step = 1; //B

bool Traveling_Sale_Man(int *s, int *g, int &cost, int &count) {
	int current_step = start_step;
	int min;
	bool check;
	while (s[current_step] == 0) {
		g[count] = current_step;
		s[current_step] = 1;
		check = false;
		min = INT_MAX;
		if (g[count] == stop_step) {
			return true;
		}
		for (int i = 0; i < 9; i++) {
			if (DT[g[count]][i] != -1 && DT[g[count]][i] < min && s[i] == 0) {
				min = DT[g[count]][i];
				current_step = i;
				check = true;
			}
		}
		if (check) {
			count++;
			cost += min;
		}
	}
	return false;
}

int main() {
	int *s = (int*)calloc(9, sizeof(int));
	int *g = (int*)calloc(9, sizeof(int));
	int cost = 0;
	int count = 0;
	if (Traveling_Sale_Man(s, g, cost, count)) {
		for (int i = 0; i <= count; i++) {
			cout << (char)(g[i] + 65);
			if (i < count) cout << " - ";
		}
		cout << "\nCost: " << cost;
	} else {
		cout << "Khong tim thay duong di";
	}
	return 0;
}