白準10971:外判員巡回2

10688 ワード
cpp テキストリンク
https://www.acmicpc.net/problem/10971

1.近接

  • はBFS関数を用いて最も早く実現された.しかしタイムアウトが発生した.いずれにしても、すべてのノードを直接巡回することは、多くの非効率をもたらすようです.
  • ですので、走り回る必要はなく、あらかじめ経路を決めて値を確認する方法だと思います.
  • のルートを事前に設定するためには、すべての都市が1回に1回、1つの都市だけが2回発生する場合であり、以前の問題で使用された順序の意味と同じである.
    =>シーケンスを利用して事前にルートを作成し、当時の費用だけを比較!

    • 2.私の回答

    #include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> cities;
int map[11][11];
int n;
int mincost=0;

void TPS() {
	int x, y;
	int cost = 0;
	for (int i = 0; i < cities.size()-1; i++) {
		x = cities[i];
		y = cities[i + 1];
		if (map[x][y] == 0)	return;
		else cost += map[x][y];
	}

	if (map[cities[cities.size() - 1]][cities[0]] != 0)	cost += map[cities[cities.size() - 1]][cities[0]];
	else return;

	mincost = min(mincost, cost);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			mincost += map[i][j]; //주의?
		}
	}

	for (int i = 0; i < n; i++) {
		cities.push_back(i);
	}

	do {
		TPS();
	} while (next_permutation(cities.begin(), cities.end()));

	cout << mincost << "\n";
	return 0;
}
    BOJ 10775空港
    [CS] React Component Day-32