// CPP program to implement traveling salesman
// problem using naive approach.
#include <bits/stdc++.h>
using namespace std;
#define V 4
// implementation of traveling Salesman Problem
int travllingSalesmanProblem(int graph[][V], int s)
{
// store all vertex apart from source vertex
vector<int> vertex;
for (int i = 0; i < V; i++)
if (i != s)
vertex.push_back(i);
// store minimum weight Hamiltonian Cycle.
int min_path = INT_MAX;
do {
// store current Path weight(cost)
int current_pathweight = 0;
// compute current path weight
int k = s;
for (int i = 0; i < vertex.size(); i++) {
current_pathweight += graph[k][vertex[i]];
k = vertex[i];
}
current_pathweight += graph[k][s];
// update minimum
min_path = min(min_path, current_pathweight);
} while (
next_permutation(vertex.begin(), vertex.end()));
return min_path;
}
// Driver Code
int main()
{
// matrix representation of graph
int graph[][V] = { { 0, 5, 10, 7 },
{ 6, 0, 11, 5 },
{ 8, 5, 0, 6 },
{ 9, 4, 11, 0 } };
int s = 0;
cout << travllingSalesmanProblem(graph, s) << endl;
return 0;
}
Ly8gQ1BQIHByb2dyYW0gdG8gaW1wbGVtZW50IHRyYXZlbGluZyBzYWxlc21hbgovLyBwcm9ibGVtIHVzaW5nIG5haXZlIGFwcHJvYWNoLgojaW5jbHVkZSA8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBWIDQKCi8vIGltcGxlbWVudGF0aW9uIG9mIHRyYXZlbGluZyBTYWxlc21hbiBQcm9ibGVtCmludCB0cmF2bGxpbmdTYWxlc21hblByb2JsZW0oaW50IGdyYXBoW11bVl0sIGludCBzKQp7CgkvLyBzdG9yZSBhbGwgdmVydGV4IGFwYXJ0IGZyb20gc291cmNlIHZlcnRleAoJdmVjdG9yPGludD4gdmVydGV4OwoJZm9yIChpbnQgaSA9IDA7IGkgPCBWOyBpKyspCgkJaWYgKGkgIT0gcykKCQkJdmVydGV4LnB1c2hfYmFjayhpKTsKCgkvLyBzdG9yZSBtaW5pbXVtIHdlaWdodCBIYW1pbHRvbmlhbiBDeWNsZS4KCWludCBtaW5fcGF0aCA9IElOVF9NQVg7CglkbyB7CgoJCS8vIHN0b3JlIGN1cnJlbnQgUGF0aCB3ZWlnaHQoY29zdCkKCQlpbnQgY3VycmVudF9wYXRod2VpZ2h0ID0gMDsKCgkJLy8gY29tcHV0ZSBjdXJyZW50IHBhdGggd2VpZ2h0CgkJaW50IGsgPSBzOwoJCWZvciAoaW50IGkgPSAwOyBpIDwgdmVydGV4LnNpemUoKTsgaSsrKSB7CgkJCWN1cnJlbnRfcGF0aHdlaWdodCArPSBncmFwaFtrXVt2ZXJ0ZXhbaV1dOwoJCQlrID0gdmVydGV4W2ldOwoJCX0KCQljdXJyZW50X3BhdGh3ZWlnaHQgKz0gZ3JhcGhba11bc107CgoJCS8vIHVwZGF0ZSBtaW5pbXVtCgkJbWluX3BhdGggPSBtaW4obWluX3BhdGgsIGN1cnJlbnRfcGF0aHdlaWdodCk7CgoJfSB3aGlsZSAoCgkJbmV4dF9wZXJtdXRhdGlvbih2ZXJ0ZXguYmVnaW4oKSwgdmVydGV4LmVuZCgpKSk7CgoJcmV0dXJuIG1pbl9wYXRoOwp9CgovLyBEcml2ZXIgQ29kZQppbnQgbWFpbigpCnsKCS8vIG1hdHJpeCByZXByZXNlbnRhdGlvbiBvZiBncmFwaAoJaW50IGdyYXBoW11bVl0gPSB7IHsgMCwgNSwgMTAsIDcgfSwKCQkJCQl7IDYsIDAsIDExLCA1IH0sCgkJCQkJeyA4LCA1LCAwLCA2IH0sCgkJCQkJeyA5LCA0LCAxMSwgMCB9IH07CglpbnQgcyA9IDA7Cgljb3V0IDw8IHRyYXZsbGluZ1NhbGVzbWFuUHJvYmxlbShncmFwaCwgcykgPDwgZW5kbDsKCXJldHVybiAwOwp9Cg==