TSP优先队列

#if 0
#include<iostream>
#include<queue>
#include<vector>
using namespace std;

class Travling {
friend void TSP(int**, int);
private:
int n;
int** dis;
int bestc;
};

struct Node {
int v;
int len;
vector<int>path;
bool temp[100] = { false };
Node(){}
Node(int v, int len) :v(v), len(len) {
path.push_back(1);
temp[1] = true;
}
bool operator < (const Node A)const {
return len > A.len;
}
};

void print(vector<int>a) {
cout << "[";
for (auto i = 0; i < a.size() - 1; i++)
cout << a[i] << ", ";
cout << a[a.size() - 1] << "]" << ‘\n‘;
}

void TSP(int** a, int n) {
Travling Y;
Y.dis = a;
Y.n = n;
Y.bestc = 9999;
priority_queue<Node>q;
q.push(Node(1, 0));
vector<int>bestpath;
while (!q.empty()) {
Node a = q.top();
q.pop();
print(a.path);
if (a.path.size() == n) {
if (a.len + Y.dis[a.v][1] < Y.bestc) {
Y.bestc = a.len + Y.dis[a.v][1];
bestpath = a.path;
}
}
for (auto i = 1; i <= n; i++) {
if (i == a.v || a.temp[i] == 1)
continue;
a.temp[i] = 1;
Node b = a;
b.v = i;
b.len += Y.dis[a.v][i];
b.path.push_back(i);
if (b.len < Y.bestc)
q.push(b);
a.temp[i] = 0;
}
}
cout << Y.bestc << ": ";
print(bestpath);
}

int main()
{
int n;
cin >> n;
int** a = new int* [n + 1];
for (auto i = 0; i <= n; i++)
a[i] = new int[n + 1];
for (auto i = 1; i <= n; i++)
for (auto j = 1; j <= n; j++)
cin >> a[i][j];
TSP(a, n);
}
/*
4
0 30 6 4
30 0 5 10
6 5 0 20

4 10 20 0
*/
#endif

TSP优先队列

原文：https://www.cnblogs.com/msboke/p/14779044.html