Fixed TSP implementation.

1 files changed, 6 insertions, 12 deletions

diff --git a/graph/TSP.cpp b/graph/TSP.cpp
index 0161d3c..7fba361 100644
--- a/graph/TSP.cpp
+++ b/graph/TSP.cpp
@@ -1,29 +1,23 @@
-// Laufzeit: O(n*2^n)
-// nodes[0] ist Start- und Endknoten.
-vector<vector<int>> dist;
+// Laufzeit: O(n^2*2^n)
+vector<vector<int>> dist; // Entfernung zwischen je zwei Punkten.
 vector<int> TSP() {
 	int n = dist.size(), m = 1 << n;
-	vector<vector<ii>> dp(n, vector<ii>(m, ii(MAX_N, -1)));
+	vector<vector<ii>> dp(n, vector<ii>(m, ii(INF, -1)));
 	
 	for(int c = 0; c < n; c++) dp[c][m-1].first = dist[c][0], dp[c][m-1].second = 0;
 
 	for(int v = m - 2; v >= 0; v--) {
 		for(int c = n - 1; c >= 0; c--) {
 			for(int g = 0; g < n; g++) { 
-				if(g != c && (((1 << g) & v) == 0)) {
+				if(g != c && !((1 << g) & v)) {
 					if((dp[g][(v | (1 << g))].first + dist[c][g]) < dp[c][v].first) {
 						dp[c][v].first = dp[g][(v | (1 << g))].first + dist[c][g];
 						dp[c][v].second = g;
-					}
-				}
-			}
-		}
-	}
+	}}}}}
 	
 	vector<int> res; res.push_back(0); int v = 0;
 	while(res.back() != 0 || res.size() == 1) {
 		res.push_back(dp[res.back()][(v |= (1 << res.back()))].second);
 	}
-	
-	return res;
+	return res; // Enthält Knoten 0 zweimal. An erster und letzter Position.
 }