재귀함수를 통해 모든 경우의수를 다 구한뒤..
min값을 출력하는 알고리즘으로 해결했습니다.
.
예를들어 3개의 도시를 방문하면

1->2->3
1->3->2
2->1->3
2->3->1
3->1->2
3->2->1

방법으로 모든 경로를 모두 체크해 보면서 최소값을 구합니다.
어떤 문제가 있을까요..

~~~ c++

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
using namespace std;
int arr[8] = { 2, 3, 5, 7, 11, 13, 17, 19 };
double a[8][8];
int mc, k;
double ret;
int solve(int u, double sum, int chack){
if (chack == mc){
ret = min(ret, sum);
return 0;
}
for (int i = 0; i < k; i++){
if (chack%arr[i] != 0){
solve(i, sum + a[u][i], chack*arr[i]);
}
}

}
int main(){
int t;
ret = 14150;
cin >> t;
while(t--){
cin >> k;
mc = 1;
for (int i = 0; i < k; i++){
mc *= arr[i];
}
for (int i = 0; i < k; i++)
{
for (int j = 0; j < k; j++){
cin >> a[i][j];
}
}
for (int i = 0; i < k; i++)
solve(i, 0, arr[i]);
printf("%.10f\n", ret);
}

return 0;

}

</spoiler>