TSP旅行商问题

// TSP.cpp: 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include "iostream"
#define NUM 100
using namespace std;

int n;
int m;
int x[NUM];
int bestx[NUM];
int cc;
int NoEdge = -1;
int a[NUM][NUM] = { {NoEdge} };
int bestc=NoEdge; 


void Backtrack(int t)
{
	if (t == n)
	{
		if (a[x[n - 1]][x[n]] != NoEdge&&a[x[n]][1] != NoEdge && (cc + a[x[n - 1]][x[n]] + a[x[n]][1] < bestc || bestc == NoEdge))
		{
			for (int i = 1; i <= n; i++)
			{
				bestx[i] = x[i];
			}
			bestc = cc += a[x[n - 1]][x[n]] + a[x[n]][1];
		}
		return;
	}
	else
	{
		for (int i = t; i <= n; i++)
		{
			if (a[x[n - 1]][x[i]] != NoEdge && (cc + a[x[t - 1]][x[i]] < bestc || bestc == NoEdge))
			{
				swap(x[t], x[i]);
				cc += a[x[t - 1]][x[t]];
				Backtrack(t + 1);
				cc -= a[x[t - 1]][x[t]];
				swap(x[t], x[i]);
			}
		}
	}
}


int main()
{
	int xl, yl, length;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) { x[i] = i; }
	for (int i = 1; i <= m; i++)
	{
		cin >> xl >> yl >> length;
		a[xl][yl] = length;
	}
	Backtrack(2);
	for (int i = 1; i <= n; i++)
	{
		cout << bestx[i] << " ";
	}
	cout << endl;
	cout << bestc << endl;
	system("pause");
    return 0;
}