BOJ|10971外販員巡回2

| Link

BOJ 10971

| Problem

海外販売員の巡回問題は英語で旅行Salesman問題(TSP)と呼ばれる問題であり、コンピュータ科学分野で最も重要な問題の一つである.様々な変種問題がありますが、最も一般的な形式の問題を見てみましょう.
1番からN番までの都市があり、都市の間に道があります.(道がないかもしれませんが)今あるセールスマンはある都市を出発して、N都市を通って、元の都市に戻るツアー旅行ルートを計画しています.でも、もう一回行った町には行けない.(最後に旅行を始めた都市に戻るのを除く)このような旅行ルートはいろいろあるかもしれませんが、最小限の旅行計画を立てたいと思っています.
行列W[i][j]の形で各パス時間の移動に要する費用が与えられる.W[i][j]は、都市iから都市jまでの料金を示す.費用は非対称です.すなわち、W[i][j]はW[j][i]とは異なる場合がある.すべての都市の費用は正の整数です.W[i][i]は常に0.場合によっては、都市iから都市jまでは不可能であり、この場合、W[i][j]=0となる.
Nと費用行列が与えられた場合、費用が最も低いセールスマンの巡回旅行経路を解くプログラムを作成します.
入力
1行目は都市の数Nを与える.(2≦N≦10)次のN行には費用行列がある.各行列の成分は1000000以下の正の整数であり、行けない場合は0を与える.W[i][j]は都市iからjまでの料金を表す.
常に巡ることができる場合のみ入力されます.
1つの都市から、すべての都市を経て、起点のすべての状況に戻ります.
最も低コスト(1都市で重複しない)

が訪れた都市はcheck
-都市数が10以下であるため、boolean check[10]

耳用

最高値更新min(answer, cost+w[node][s_node] // s_node == start node-訪問都市数==合計都市数count == n最初の都市に戻らなければなりませんw[node][s_node] != 0 // s_node == start node

| Code

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
using namespace std;

bool check[10] = {0,};
int answer = 999999999;
int w[10][10];
int n, s_node;

void DFS(int node, int cost, int count) {
	if(count == n)
		if (w[node][s_node])
		{
			answer = min(answer, cost + w[node][s_node]);
		}
	for (int i = 0; i < n; i++)
	{
		if (check[i] == false && w[node][i] != 0)
		{
			check[i] = true;
			DFS(i, cost + w[node][i], count + 1);
			check[i] = false;
		}
	}
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
			scanf("%d", &w[i][j]);
	}
	for (int i = 0; i < n; i++)
	{
		s_node = i;
		check[i] = true;
		DFS(i,0,1);
		check[i] = false;
	}
	printf("%d", answer);
}

| Result