TSP1 - Traveling Salesman Problem 1

<script type="syntaxhighlighter" class="brush: cpp;"><![CDATA[
#include <fstream>
#include <iostream>
#include <iomanip>
#include <algorithm>
using namespace std;

int numVertex;

double hamilton(double **distance);

int main(void)
{
 ifstream fin("example.inp");
 int testCase;
 fin >> testCase;

 while (testCase--)
 {
  fin >> numVertex;
  // N * N 크기의 2차원 배열 동적할당
  double **distance = new double*[numVertex];
  for (int i = 0; i < numVertex; i++)
   distance[i] = new double[numVertex];

  for (int i = 0; i < numVertex; i++)
   for (int j = 0; j < numVertex; j++)
    fin >> distance[i][j];

  cout << fixed << setprecision(10) << hamilton(distance) << endl;
 }
 return 0;
}

double hamilton(double **distance)
{
 int *c = new int[numVertex];
 double result = 9999999999.9;
 for (int i = 0; i < numVertex; i++)
  c[i] = i;

 do
 {
  double temp = 0.0;
  for (int i = 0; i < numVertex-1; i++)
   temp += distance[c[i]][c[i+1]];

  if (result > temp)
   result = temp;
 } while (next_permutation(c, c + numVertex));
 return result;
}
]]></script>